Combinatorial Optimization Submissions  2008
January 2008
Polyhedra
Size constrained graph partitioning polytope. Part I: Dimension and trivial facets
Aykut Özsoy, Martine Labbé
Polyhedra
Size constrained graph partitioning polytope. Part II: Nontrivial facets
F. Aykut Özsoy, Martine Labbé
Polyhedra
A Polyhedral Study of the Network Pricing Problem with Connected Toll Arcs
Géraldine Heilporn, Martine Labbé, Patrice Marcotte, Gilles Savard
Graphs and Matroids
An algorithm to determine the clique number of a graph
Omar Kettani
Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
Jesus A. De Loera, Jon Lee, Peter Malkin, Susan Margulies
February 2008
Fast Local Search for the Maximum Independent Set Problem
Diogo V. Andrade, Mauricio G. C. Resende, Renato F. Werneck
Meta Heuristics
GRASP and path relinking for the maxmin diversity problem
Mauricio G. C. Resende, Rafael Martí, Micael Gallego, Abraham Duarte
Graphs and Matroids
Tur\'an Graphs, Stability Number, and Fibonacci Index
Hadrien Mélot, Véronique Bruyčre
March 2008
Meta Heuristics
The twostage recombination operator and its application to the multiobjective 0/1 knapsack problem: a comparative study
B. AGHEZZAF, M. NAIMI
April 2008
Branch and Cut Algorithms
A Hybrid RelaxandCut/BranchandCut Algorithm for the DegreeConstrained Minimum Spanning Tree Problem
Alexandre Salles da Cunha, Abilio Lucena
Meta Heuristics
Metaheuristic hybridization with GRASP
Mauricio G. C. Resende
Graphs and Matroids
Copositive programming motivated bounds on
the stability and the chromatic numbers
Igor Dukanovic, Franz Rendl
May 2008
Nonlinear Optimization over a Weighted Independence System
Jon Lee, Shmuel Onn, Robert Weismantel
Other
New Turnpike Theorems for the Unbounded Knapsack Problem
Ping H. Huang, Thomas L. Morin
Other
An Improved Algorithm for the Generalized Quadratic Assignment Problem
Artur Pessoa, Peter Hahn, Monique Guignard, YiRong Zhu
Graphs and Matroids
A Dynamic Programming Framework for Combinatorial Optimization Problems on Graphs with Bounded Pathwidth
Mugurel Ionut Andreica
June 2008
Branch and Cut Algorithms
A Branchandcut Algorithm for Integer Bilevel Linear Programs
Scott Denegre, Ted Ralphs
On Newton(like) inequalities for multivariate homogeneous polynomials
Leonid Gurvits
Approximation Algorithms
An FPTAS for Minimizing the Product of Two Nonnegative Linear Cost Functions
Vineet Goyal, Latife Genc Kaya, R. Ravi
A Robust BranchCutandPrice Algorithm for the Heterogeneous Fleet Vehicle Routing Problem
Artur Pessoa, Eduardo Uchoa, Marcus Poggi de Aragăo
Robust BranchCutandPrice Algorithms for Vehicle Routing Problems
Artur Pessoa, Marcus Poggi de Aragăo, Eduardo Uchoa
Meta Heuristics
An annotated bibliography of GRASP, Part I: Algorithms
Paola Festa, Mauricio G. C. Resende
Meta Heuristics
An annotated bibliography of GRASP, Part II: Applications
Paola Festa, Mauricio G. C. Resende
July 2008
BranchandPrice for LargeScale Capacitated Hub Location Problems with Single Assignment
Ivan Contreras, Juan A. Díaz, Elena Fernández
Meta Heuristics
GRASP: Advances and applications
Mauricio G. C. Resende, Celso C. Ribeiro
Meta Heuristics
GRASP
Mauricio G. C. Resende, Celso C. Ribeiro
Meta Heuristics
GRASP: Basic components and enhancements
Paola Festa, Mauricio G. C. Resende
Meta Heuristics
Hybrid GRASP heuristics
Paola Festa, Mauricio G. C. Resende
Further results on knapsack tightening with guaranteed bounds
Daniel Bienstock
Nonlinear optimization for matroid intersection and extensions
Yael Berstein, Jon Lee, Shmuel Onn, Robert Weismantel
August 2008
NearOptimal Solutions and Integrality Gaps for Almost All Instances of SingleMachine PrecedenceConstrained Scheduling
Andreas S. Schulz, Nelson A. Uhan
September 2008
Meta Heuristics
Test problems for quasisatellite packing: Cylinders packing with behavior constraints and all the optimal solutions known
Chao Che, Yishou Wang, Hongfei Teng
Other
A Level3 Reformulationlinearization Technique Bound for the Quadratic Assignment Problem
Peter M. Hahn, YiRong Zhu, Monique Guignard, William L. Hightower
Detecting Critical Nodes in Sparse Graphs
Ashwin Arulselvan, Clayton Commander, Lily Elefteriadou, Panos Pardalos
October 2008
Other
Latticebased Algorithms for Number Partitioning in the Hard Phase
Bala Krishnamoorthy, William Webb, Nathan Moyer
Maximizing Nonmonotone Submodular Functions under Matroid and Knapsack Constraints
Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko
Graphs and Matroids
The Knapsack Problem with Conflict Graphs
Ulrich Pferschy, Joachim Schauer
November 2008
Graphs and Matroids
Fibonacci Index and Stability Number of Graphs: a Polyhedral Study
V. Bruyčre, H. Mélot
Efficient highprecision dense matrix algebra on parallel architectures for nonlinear discrete optimization
John Gunnels, Jon Lee, Susan Margulies
Approximation Algorithms
Minimizing the sum of weighted completion times in a concurrent open shop
Monaldo Mastrolilli, Maurice Queyranne, Andreas S. Schulz, Ola Svensson, Nelson A. Uhan
December 2008
Effective formulation reductions for the quadratic assignment problem
Huizhen Zhang, Cesar BeltranRoyo, Miguel Constantino
