Applications of Discrepancy Theory in Multiobjective Approximation
  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. 
Christian Gla{\ss}er, Christian Reitwie{\ss}ner, Maximilian Witek
cs.DS cs.CC