On the Complexity of Master Problems

M. van Ee, R.A. Sitters

Research output: Contribution to JournalArticleAcademicpeer-review


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 languageEnglish
Pages (from-to)567-576
JournalLecture Notes in Computer Science
Publication statusPublished - 2015
Event40th International Symposium on Mathematical Foundations of Computer Science - Berlin
Duration: 24 Aug 201528 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


Dive into the research topics of 'On the Complexity of Master Problems'. Together they form a unique fingerprint.

Cite this