10.4230/LIPICS.FSTTCS.2011.55
Glaßer, Christian
Christian
Glaßer
Reitwießner, Christian
Christian
Reitwießner
Witek, Maximilian
Maximilian
Witek
Applications of Discrepancy Theory in Multiobjective Approximation
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2011
Article
Discrepancy Theory
Multiobjective Optimization
Satisfiability
Traveling Salesman
Chakraborty, Supratik
Supratik
Chakraborty
Kumar, Amit
Amit
Kumar
2011
2011-12-01
2011-12-01
2011-12-01
en
urn:nbn:de:0030-drops-33233
10.4230/LIPIcs.FSTTCS.2011
978-3-939897-34-7
1868-8969
10.4230/LIPIcs.FSTTCS.2011
LIPIcs, Volume 13, FSTTCS 2011
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
2013
13
10
55
65
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Chakraborty, Supratik
Supratik
Chakraborty
Kumar, Amit
Amit
Kumar
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2011
13
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
11 pages
430812 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
We apply a multi-color extension of the Beck-Fiala theorem to show that the multiobjective maximum traveling salesman problem is randomized 1/2-approximable on directed graphs and randomized 2/3-approximable on undirected graphs. Using the same technique we show that the multiobjective maximum satisfiablilty problem is 1/2-approximable.
LIPIcs, Vol. 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), pages 55-65