Integer Programming: Optimization and Evaluation Are Equivalent

DOI10.1007/978-3-642-03367-4_45MaRDI QIDQ3183481zbMATH OpenOpenAlexDBLPWikidataFDO

Authors James B. Orlin, Abraham P. Punnen, Andreas S. Schulz

Publication date 20 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03367-4_45

Mathematics Subject Classification ID

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

Recommendations

• 0/1-Integer programming: Optimization and Augmentation are equivalent
• Integer programming as a framework for optimization and approximability
• How easy is local search?
• On the relative complexity of 15 problems related to~0/1-integer programming
• scientific article; zbMATH DE number 3885655

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 2064409 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 863497 (Why is no real title available?)
• Approximate Local Search in Combinatorial Optimization
• Calculation of stability radii for combinatorial optimization problems
• How easy is local search?
• Network flows. Theory, algorithms, and applications.
• On the complexity of postoptimality analysis of 0/1 programs
• On the relative complexity of 15 problems related to~0/1-integer programming
• Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
• Simple Local Search Problems that are Hard to Solve
• The NP-completeness column: finding needles in haystacks
• The complexity of pure Nash equilibria

Cited in

(6)

• On the relative complexity of 15 problems related to~0/1-integer programming
• A generalized simplex method for integer problems given by verification oracles
• 0/1-Integer programming: Optimization and Augmentation are equivalent
• Neighborhood persistency of the linear optimization relaxation of integer linear optimization
• Order preserving reductions and polynomial improving paths
• The design of exponential neighborhoods -- a primal approach to integer programming.

This page was built for publication: Integer Programming: Optimization and Evaluation Are Equivalent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3183481)