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 satis...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2011-07
Main Authors: Glaßer, Christian, Reitwießner, Christian, Witek, Maximilian
Format: Article
Language:English
Subjects:
Graph theory
Graphs
Multiple objective analysis
Randomization
Traveling salesman problem
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422