LIPIcs.FSTTCS.2011.55.pdf
- Filesize: 420 kB
- 11 pages
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.
Feedback for Dagstuhl Publishing