Integer Programming and Combinatorial Optimization

A Faster Scaling Algorithm for Minimizing Submodular Functions.- A Generalization of Edmonds' Matching and Matroid Intersection Algorithms.- A Coordinatewise Domain Scaling Algorithm for M-convex Function Minimization.- The Quickest Multicommodity Flow Problem.- A New Min-Cut Max-Flow Ratio for Multicommodity Flows.- Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems.- Finding the Exact Integrality Gap for Small Traveling Salesman Problems.- Polynomial-Time Separation of Simple Comb Inequalities.- A New Approach to Cactus Construction Applied to TSP Support Graphs.- Split Closure and Intersection Cuts.- An Exponential Lower Bound on the Length of Some Classes of Branch-and-Cut Proofs.- Lifted Inequalities for 0-1 Mixed Integer Programming: Basic Theory and Algorithms.- On a Lemma of Scarf.- A Short Proof of Seymour's Characterization of the Matroids with the Max-Flow Min-Cut Property.- Integer Programming and Arrovian Social Welfare Functions.- Integrated Logistics: Approximation Algorithms Combining Facility Location and Network Design.- The Minimum Latency Problem Is NP-Hard for Weighted Trees.- An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem.- A Polyhedral Approach to Surface Reconstruction from Planar Contours.- The Semidefinite Relaxation of the k-Partition Polytope Is Strong.- A Polyhedral Study of the Cardinality Constrained Knapsack Problem.- A PTAS for Minimizing Total Completion Time of Bounded Batch Scheduling.- An Approximation Scheme for the Two-Stage, Two-Dimensional Bin Packing Problem.- On Preemptive Resource Constrained Scheduling: Polynomial-Time Approximation Schemes.- Hard Equality Constrained Integer Knapsacks.- The Distribution of Values in the Quadratic Assignment Problem.- A NewSubadditive Approach to Integer Programming.- Improved Approximation Algorithms for Resource Allocation.- Approximating the Advertisement Placement Problem.- Algorithms for Minimizing Response Time in Broadcast Scheduling.- Building Edge-Failure Resilient Networks.- The Demand Matching Problem.- The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap.