Applications of Discrepancy Theory in Multiobjective Approximation

Details Applications of Discrepancy Theory in Multiobjective Approximation Applications of Discrepancy Theory in Multiobjective Approximation

2011-07-04

arxiv.org/abs/1107.0634v1

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Applications of Discrepancy Theory in Multiobjective Approximation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Applications of Discrepancy Theory in Multiobjective Approximation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Applications of Discrepancy Theory in Multiobjective Approximation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-4274