Exponential-Time Approximation of Hard Problems

Details Exponential-Time Approximation of Hard Problems Exponential-Time Approximation of Hard Problems

2008-10-27

arxiv.org/abs/0810.4934v1

Computer Science

Data Structures and Algorithms

Scientific paper

We study optimization problems that are neither approximable in polynomial time (at least with a constant factor) nor fixed parameter tractable, under widely believed complexity assumptions. Specifically, we focus on Maximum Independent Set, Vertex Coloring, Set Cover, and Bandwidth. In recent years, many researchers design exact exponential-time algorithms for these and other hard problems. The goal is getting the time complexity still of order $O(c^n)$, but with the constant $c$ as small as possible. In this work we extend this line of research and we investigate whether the constant $c$ can be made even smaller when one allows constant factor approximation. In fact, we describe a kind of approximation schemes -- trade-offs between approximation factor and the time complexity. We study two natural approaches. The first approach consists of designing a backtracking algorithm with a small search tree. We present one result of that kind: a $(4r-1)$-approximation of Bandwidth in time $O^*(2^{n/r})$, for any positive integer $r$. The second approach uses general transformations from exponential-time exact algorithms to approximations that are faster but still exponential-time. For example, we show that for any reduction rate $r$, one can transform any $O^*(c^n)$-time algorithm for Set Cover into a $(1+\ln r)$-approximation algorithm running in time $O^*(c^{n/r})$. We believe that results of that kind extend the applicability of exact algorithms for NP-hard problems.

Affiliated with

Also associated with

No associations

Rating

Exponential-Time Approximation of Hard Problems 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 Exponential-Time Approximation of Hard Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exponential-Time Approximation of Hard Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-484823