Information Technology

Approximation Algorithms

---

NP-hard optimization problems exhibit a rich set of possibilities, all the way from allowing approximability to any required degree, to essentially not allowing approximability at all. Despite this diversity, underlying the process of design of approximation algorithms are some common principles. We will explore these in the current chapter.
An optimization problem is polynomial time solvable only if it has the algorithmically relevant combinatorial structure that can be used as “footholds” to efficiently home in on an optimal solution. The process of designing an exact polynomial time algorithm is a two-pronged attack: un- raveling this structure in the problem and finding algorithmic techniques that can exploit this structure.
Although NP-hard optimization problems do not offer footholds for find- ing optimal solutions efficiently, they may still offer footholds for finding near-optimal solutions efficiently. So, at a high level, the process of design of approximation algorithms is not very different from that of design of exact algorithms. It still involves unraveling the relevant structure and finding al- gorithmic techniques to exploit it. Typically, the structure turns out to be more elaborate, and often the algorithmic techniques result from generalizing and extending some of the powerful algorithmic tools developed in the study of exact algorithms.
On the other hand, looking at the process of designing approximation algorithms a little more closely, one can see that it has its own general princi- ples. We illustrate some of these principles in Section 1.1, using the following simple setting

---

Availability

No copy data

Detail Information

Series Title

Approximation Algorithms

Call Number

-

Publisher

USA : Springer Berlin Heidelberg NewYork., 2001

Collation

1-396

Language

English

ISBN/ISSN

-

Classification

NONE

Content Type

-

Media Type

-

Carrier Type

-

Edition

1st Edtion

Subject(s)

Technology

Specific Detail Info

-

Statement of Responsibility

-

Other version/related

File Attachment

Comments

---

You must be logged in to post a comment