| 1996 | Primal-Dual Approximation Algorithms for Feedback Problems. | Michel X. Goemans, David P. Williamson |
| 1996 | The Strongest Facets of the Acyclic Subgraph Polytope Are Unknown. | Michel X. Goemans, Leslie A. Hall |
| 1996 | A Supermodular Relaxation for Scheduling with Release Dates. | Michel X. Goemans |
| 1996 | A Polyhedral Approach to the Feedback Vertex Set Problem. | Meinrad Funke, Gerhard Reinelt |
| 1996 | Separating Maximally Violated Comb Inequalities in Planar Graphs. | Lisa Fleischer, va Tardos |
| 1996 | A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees. | Sndor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal E. Young |
| 1996 | On Optimizing Multiplications of Sparse Matrices. | Edith Cohen |
| 1996 | Algorithms and Extended Formulations for One and Two Facility Network Design. | Sunil Chopra, Itzhak Gilboa, S. Trilochan Sastry |
| 1996 | Coloring Bipartite Hypergraphs. | Hui Chen, Alan M. Frieze |
| 1996 | Separating over Classes of TSP Inequalities Defined by 0 Node-Lifting in Polynominal Time. | Robert Carr |
| 1996 | A Heuristic Algorithm for the Set Covering Problem. | Alberto Caprara, Matteo Fischetti, Paolo Toth |
| 1996 | The Travelling Salesman and the PQ-Tree. | Rainer E. Burkard, Vladimir G. Deineko, Gerhard J. Woeginger |
| 1996 | The Quadratic Assignment Problem with a Monotone Anti-Monge and a Symmetric Toeplitz Matrix: Easy and Hard Cases. | Rainer E. Burkard, Eranda ela, Gnter Rote, Gerhard J. Woeginger |
| 1996 | On Dependent Randomized Rounding Algorithms. | Dimitris Bertsimas, Chung-Piaw Teo, Rakesh Vohra |
| 1996 | Integer Muticommodity Flow Problems. | Cynthia Barnhart, Christopher A. Hane, Pamela H. Vance |
| 1996 | Colourful Linear Programming. | Imre Brny, Shmuel Onn |
| 1996 | Continuous Relaxations for Constrained Maximum-Entropy Sampling. | Kurt M. Anstreicher, Marcia Fampa, Jon Lee, Joy Williams |
| 1995 | Scheduling Unit Jobs with Compatible Release Dates on Parallel Machines with Nonstationary Speeds. | Maurice Queyranne, Andreas S. Schulz |
| 1995 | A Minimal Algorithm for the Bounded Knapsack Problem. | David Pisinger |
| 1995 | The Random Linear Bottleneck Assignment Problem. | Ulrich Pferschy |
| 1995 | On Combinatorial Properties of Binary Spaces. | Beth Novick, Andrs Seb |
| 1995 | (0, ±1) Ideal Matrices. | Paolo Nobili, Antonio Sassano |
| 1995 | A Faster Edge Splitting Algorithm in Multigraphs and its Application to the Edge-Connectivity Augmentation Problem. | Hiroshi Nagamochi, Toshihide Ibaraki |
| 1995 | The Interval Order Polytope of a Digraph. | Rudolf Mller, Andreas S. Schulz |
| 1995 | The Hilbert Basis of the Cut Cone over the Complete Graph | Franois Laburthe |