On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming

DOI10.1007/978-3-540-76796-1_19zbMath1359.90160OpenAlexW166153989MaRDI QIDQ2971619

Andreas S. Schulz

Publication date: 7 April 2017

Published in: Research Trends in Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-76796-1_19

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

Integer Programming: Optimization and Evaluation Are Equivalent ⋮ A scaling algorithm for optimizing arbitrary functions over vertices of polytopes ⋮ Extended formulations for radial cones ⋮ A Generalized Simplex Method for Integer Problems Given by Verification Oracles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
• An application of simultaneous diophantine approximation in combinatorial optimization
• How easy is local search?
• The directed subgraph homeomorphism problem
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• Neighborhood search algorithms for guaranteeing optimal traveling salesman tours must be inefficient
• On the complexity of postoptimality analysis of \(0/1\) programs
• Test sets of integer programs
• Calculation of stability radii for combinatorial optimization problems
• Primal separation for 0/1 polytopes
• Primal cutting plane algorithms revisited
• The Hirsch conjecture is true for (0,1)-polytopes
• Inverse Optimization
• Hill Climbing with Multiple Local Optima
• On the symmetric travelling salesman problem: A computational study
• On the Complexity of Local Search for the Traveling Salesman Problem
• Lectures on Polytopes
• Approximate Local Search in Combinatorial Optimization
• A Simplified Primal (All-Integer) Integer Programming Algorithm
• The Complexity of Generic Primal Algorithms for Solving General Integer Programs
• Combinatorial optimization. Theory and algorithms.