Name
Abstract | ||
|---|---|---|
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 satisfiabilty problem is 1/2-approximable |
Year | DOI | Venue |
|---|---|---|
2011 | 10.4230/LIPIcs.FSTTCS.2011.55 | Leibniz International Proceedings in Informatics |
Keywords | DocType | Volume |
Discrepancy Theory,Multiobjective Optimization,Satisfiability,Traveling Salesman | Conference | 13 |
ISSN | Citations | PageRank |
1868-8969 | 2 | 0.37 |
References | Authors | |
14 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christian Glaßer | 1 | 175 | 24.52 |
| Christian Reitwießner | 2 | 39 | 4.81 |
| Maximilian Witek | 3 | 25 | 3.71 |