Optimization Online


Combinatorial Optimization Submissions - 2008

January 2008

Size constrained graph partitioning polytope. Part I: Dimension and trivial facets
Aykut Özsoy, Martine Labbé

Size constrained graph partitioning polytope. Part II: Non-trivial facets
F. Aykut Özsoy, Martine Labbé

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 max-min 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 two-stage recombination operator and its application to the multiobjective 0/1 knapsack problem: a comparative study

April 2008

Branch and Cut Algorithms
A Hybrid Relax-and-Cut/Branch-and-Cut Algorithm for the Degree-Constrained 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

New Turnpike Theorems for the Unbounded Knapsack Problem
Ping H. Huang, Thomas L. Morin

An Improved Algorithm for the Generalized Quadratic Assignment Problem
Artur Pessoa, Peter Hahn, Monique Guignard, Yi-Rong 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 Branch-and-cut 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 Non-negative Linear Cost Functions
Vineet Goyal, Latife Genc Kaya, R. Ravi

A Robust Branch-Cut-and-Price Algorithm for the Heterogeneous Fleet Vehicle Routing Problem
Artur Pessoa, Eduardo Uchoa, Marcus Poggi de Aragăo

Robust Branch-Cut-and-Price 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

Branch-and-Price for Large-Scale 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
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

Near-Optimal Solutions and Integrality Gaps for Almost All Instances of Single-Machine Precedence-Constrained Scheduling
Andreas S. Schulz, Nelson A. Uhan

September 2008

Meta Heuristics
Test problems for quasi-satellite packing: Cylinders packing with behavior constraints and all the optimal solutions known
Chao Che, Yi-shou Wang, Hong-fei Teng

A Level-3 Reformulation-linearization Technique Bound for the Quadratic Assignment Problem
Peter M. Hahn, Yi-Rong Zhu, Monique Guignard, William L. Hightower

Detecting Critical Nodes in Sparse Graphs
Ashwin Arulselvan, Clayton Commander, Lily Elefteriadou, Panos Pardalos

October 2008

Lattice-based Algorithms for Number Partitioning in the Hard Phase
Bala Krishnamoorthy, William Webb, Nathan Moyer

Maximizing Non-monotone 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 high-precision 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 Beltran-Royo, Miguel Constantino

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society