On the relative complexity of 15 problems related to 0/1-integer programming

Andreas S. Schulz

doi:10.1007/978-3-540-76796-1_19

On the relative complexity of 15 problems related to 0/1-integer programming

Andreas S. Schulz

Massachusetts Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

6 Scopus citations

Abstract

An integral part of combinatorial optimization and computational complexity consists of establishing relationships between different problems or different versions of the same problem. In this chapter, we bring together known and new, previously published and unpublished results, which establish that 15 problems related to optimizing a linear function over a 0/1-polytope are polynomial-time equivalent. This list of problems includes optimization and augmentation, testing optimality and primal separation, sensitivity analysis and inverse optimization, as well as several others.

Original language	English
Title of host publication	Research Trends in Combinatorial Optimization
Subtitle of host publication	Bonn 2008
Publisher	Springer Berlin Heidelberg
Pages	399-428
Number of pages	30
ISBN (Print)	9783540767954
DOIs	https://doi.org/10.1007/978-3-540-76796-1_19
State	Published - 2009
Externally published	Yes

Access to Document

10.1007/978-3-540-76796-1_19

Cite this

@inbook{b75bc2d03853495782db7399d774c69b,

title = "On the relative complexity of 15 problems related to 0/1-integer programming",

abstract = "An integral part of combinatorial optimization and computational complexity consists of establishing relationships between different problems or different versions of the same problem. In this chapter, we bring together known and new, previously published and unpublished results, which establish that 15 problems related to optimizing a linear function over a 0/1-polytope are polynomial-time equivalent. This list of problems includes optimization and augmentation, testing optimality and primal separation, sensitivity analysis and inverse optimization, as well as several others.",

author = "Schulz, \{Andreas S.\}",

year = "2009",

doi = "10.1007/978-3-540-76796-1\_19",

language = "English",

isbn = "9783540767954",

pages = "399--428",

booktitle = "Research Trends in Combinatorial Optimization",

publisher = "Springer Berlin Heidelberg",

}

TY - CHAP

T1 - On the relative complexity of 15 problems related to 0/1-integer programming

AU - Schulz, Andreas S.

PY - 2009

Y1 - 2009

N2 - An integral part of combinatorial optimization and computational complexity consists of establishing relationships between different problems or different versions of the same problem. In this chapter, we bring together known and new, previously published and unpublished results, which establish that 15 problems related to optimizing a linear function over a 0/1-polytope are polynomial-time equivalent. This list of problems includes optimization and augmentation, testing optimality and primal separation, sensitivity analysis and inverse optimization, as well as several others.

AB - An integral part of combinatorial optimization and computational complexity consists of establishing relationships between different problems or different versions of the same problem. In this chapter, we bring together known and new, previously published and unpublished results, which establish that 15 problems related to optimizing a linear function over a 0/1-polytope are polynomial-time equivalent. This list of problems includes optimization and augmentation, testing optimality and primal separation, sensitivity analysis and inverse optimization, as well as several others.

UR - https://www.scopus.com/pages/publications/69949168224

U2 - 10.1007/978-3-540-76796-1_19

DO - 10.1007/978-3-540-76796-1_19

M3 - Chapter

AN - SCOPUS:69949168224

SN - 9783540767954

SP - 399

EP - 428

BT - Research Trends in Combinatorial Optimization

PB - Springer Berlin Heidelberg

ER -

On the relative complexity of 15 problems related to 0/1-integer programming

Abstract

Access to Document

Other files and links

Fingerprint

Cite this