Computer Science – Data Structures and Algorithms
Scientific paper
2009-09-10
Computer Science
Data Structures and Algorithms
13 pages, 3 figures. To appear at 21st ACM-SIAM Symp. Discrete Algorithms (SODA 2010)
Scientific paper
This paper considers pairs of optimization problems that are defined from a single input and for which it is desired to find a good approximation to either one of the problems. In many instances, it is possible to efficiently find an approximation of this type that is better than known inapproximability lower bounds for either of the two individual optimization problems forming the pair. In particular, we find either a $(1+\epsilon)$-approximation to $(1,2)$-TSP or a $1/\epsilon$-approximation to maximum independent set, from a given graph, in linear time. We show a similar paired approximation result for finding either a coloring or a long path. However, no such tradeoff exists in some other cases: for set cover and hitting set problems defined from a single set family, and for clique and independent set problems on the same graph, it is not possible to find an approximation when both problems are combined that is better than the best approximation for either problem on its own.
No associations
LandOfFree
Paired approximation problems and incompatible inapproximabilities 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 Paired approximation problems and incompatible inapproximabilities, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Paired approximation problems and incompatible inapproximabilities will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-131206