On the Complexity of Master Problems

M. van Ee; R.A. Sitters

doi:10.1007/978-3-662-48054-0_47

On the Complexity of Master Problems

M. van Ee, R.A. Sitters

Amsterdam Business Research Institute

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

A master solution for an instance of a combinatorial problem is a solution with the property that it is optimal for any sub instance. For example, a master tour for an instance of the TSP problem has the property that restricting the solution to any subset S results in an optimal solution for S. The problem of deciding if a TSP instance has a master tour is known to be polynomially solvable. Here, we show that the master tour problem is Δ

Original language	English
Pages (from-to)	567-576
Journal	Lecture Notes in Computer Science
Volume	9235
DOIs	https://doi.org/10.1007/978-3-662-48054-0_47
Publication status	Published - 2015
Event	40th International Symposium on Mathematical Foundations of Computer Science - Berlin Duration: 24 Aug 2015 → 28 Aug 2015

Bibliographical note

Proceedings title: Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II
Publisher: Springer
Place of publication: Berlin
ISBN: 978-3-662-48053-3
Editors: G.F. Italiano, G. Pighizzini, D.T. Sannella

Access to Document

10.1007/978-3-662-48054-0_47

Persistent URL (handle)

Persistent link

Cite this

@article{06dd71c9695b40c5a3f7cff93b81a868,

title = "On the Complexity of Master Problems",

abstract = "A master solution for an instance of a combinatorial problem is a solution with the property that it is optimal for any sub instance. For example, a master tour for an instance of the TSP problem has the property that restricting the solution to any subset S results in an optimal solution for S. The problem of deciding if a TSP instance has a master tour is known to be polynomially solvable. Here, we show that the master tour problem is Δ",

author = "{van Ee}, M. and R.A. Sitters",

note = "Proceedings title: Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II Publisher: Springer Place of publication: Berlin ISBN: 978-3-662-48053-3 Editors: G.F. Italiano, G. Pighizzini, D.T. Sannella; 40th International Symposium on Mathematical Foundations of Computer Science ; Conference date: 24-08-2015 Through 28-08-2015",

year = "2015",

doi = "10.1007/978-3-662-48054-0_47",

language = "English",

volume = "9235",

pages = "567--576",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

}

TY - JOUR

T1 - On the Complexity of Master Problems

AU - van Ee, M.

AU - Sitters, R.A.

N1 - Proceedings title: Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II Publisher: Springer Place of publication: Berlin ISBN: 978-3-662-48053-3 Editors: G.F. Italiano, G. Pighizzini, D.T. Sannella

PY - 2015

Y1 - 2015

N2 - A master solution for an instance of a combinatorial problem is a solution with the property that it is optimal for any sub instance. For example, a master tour for an instance of the TSP problem has the property that restricting the solution to any subset S results in an optimal solution for S. The problem of deciding if a TSP instance has a master tour is known to be polynomially solvable. Here, we show that the master tour problem is Δ

AB - A master solution for an instance of a combinatorial problem is a solution with the property that it is optimal for any sub instance. For example, a master tour for an instance of the TSP problem has the property that restricting the solution to any subset S results in an optimal solution for S. The problem of deciding if a TSP instance has a master tour is known to be polynomially solvable. Here, we show that the master tour problem is Δ

U2 - 10.1007/978-3-662-48054-0_47

DO - 10.1007/978-3-662-48054-0_47

M3 - Article

SN - 0302-9743

VL - 9235

SP - 567

EP - 576

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 40th International Symposium on Mathematical Foundations of Computer Science

Y2 - 24 August 2015 through 28 August 2015

ER -

On the Complexity of Master Problems

Abstract

Bibliographical note

Access to Document

Persistent URL (handle)

Fingerprint

Cite this