Skip to main content
main-content

Über dieses Buch

This book is intended to be used as a textbook for graduate students studying theoretical computer science. It can also be used as a reference book for researchers in the area of design and analysis of approximation algorithms. Design and Analysis of Approximation Algorithms is a graduate course in theoretical computer science taught widely in the universities, both in the United States and abroad. There are, however, very few textbooks available for this course. Among those available in the market, most books follow a problem-oriented format; that is, they collected many important combinatorial optimization problems and their approximation algorithms, and organized them based on the types, or applications, of problems, such as geometric-type problems, algebraic-type problems, etc. Such arrangement of materials is perhaps convenient for a researcher to look for the problems and algorithms related to his/her work, but is difficult for a student to capture the ideas underlying the various algorithms. In the new book proposed here, we follow a more structured, technique-oriented presentation. We organize approximation algorithms into different chapters, based on the design techniques for the algorithms, so that the reader can study approximation algorithms of the same nature together. It helps the reader to better understand the design and analysis techniques for approximation algorithms, and also helps the teacher to present the ideas and techniques of approximation algorithms in a more unified way.

Inhaltsverzeichnis

Frontmatter

1. Introduction

Abstract
When exact solutions are hard to compute, approximation algorithms can help. In this chapter, we introduce the basic notions of approximation algorithms.We study a simple optimization problem to demonstrate the tradeoff between the time complexity and performance ratio of its approximation algorithms. We also present a brief introduction to the general theory of computational complexity and show how to apply this theory to classify optimization problems according to their approximability.
Ding-Zhu Du, Ker-I Ko, Xiaodong Hu

2. Greedy Strategy

Abstract
The greedy strategy is a simple and popular idea in the design of approximation algorithms. In this chapter, we study two general theories, based on the notions of independent systems and submodular potential functions, about the analysis of greedy algorithms, and present a number of applications of these methods.
Ding-Zhu Du, Ker-I Ko, Xiaodong Hu

3. Restriction

Abstract
When we design an approximate algorithm by the restriction method, we add some constraints on an optimization problem to shrink the feasible domain so that the optimization problemon the resulting domain becomes easier to solve or approximate. We may then use the optimal or approximate solutions for this restricted problem to approximate the original problem.
Ding-Zhu Du, Ker-I Ko, Xiaodong Hu

4. Partition

Abstract
The basic idea of partition is to divide the input object into smaller parts so that each part has a simple solution, and a feasible solution to the input instance can be constructed by combining the solutions of the smaller parts. The method of partition can be seen as a special form of restriction; that is, we restrict our attention to the feasible solutions that can be constructed through partitions.
Ding-Zhu Du, Ker-I Ko, Xiaodong Hu

5. Guillotine Cut

Abstract
Guillotine cut is a technique of adaptive partition that has found interesting applications in many geometric problems. Roughly speaking, a guillotine cut is a subdivision by a straight line that partitions a given area into at least two subareas. By a sequence of guillotine cut operations, we can partition the input area into smaller areas, solve the subproblems in these smaller areas, and combine these solutions to obtain a feasible solution to the original input.
Ding-Zhu Du, Ker-I Ko, Xiaodong Hu

6. Relaxation

Abstract
An optimization problem asks for a solution from a given feasible domain that provides the optimal value of a given objective function. The technique of relaxation is, contrary to the technique of restriction, to relax some constraints on the feasible solutions and, hence, enlarge the feasible domain so that an optimal or a good approximate solution to the relaxed version of the problemcan be found in polynomial time. This optimal or approximate solution to the relaxed version is not necessarily feasible for the original problem, and we may need to modify it to get a feasible solution to the original input. This modification step often requires special tricks and is an important part of the relaxation technique.
Ding-Zhu Du, Ker-I Ko, Xiaodong Hu

7. Linear Programming

Abstract
A widely used relaxation technique for approximation algorithms is to convert an optimization problem into an integer linear program and then relax the constraints on the solutions allowing them to assume real, noninteger values. As the optimal solution to a (real-valued) linear program can be found in polynomial time, we can then solve the linear program and round the solutions to integers as the solutions for the original problem. In this chapter, we give a brief introduction to the theory of linear programming and discuss various rounding techniques.
Ding-Zhu Du, Ker-I Ko, Xiaodong Hu

8. Primal-Dual Schema and Local Ratio

Abstract
Based on the duality theory of linear programming, a new approximation technique, called the primal-dual schema, has been developed. With this technique, we do not need to compute the optimal solution of the relaxed linear program in order to get an approximate solution of the integer program. Thus, we can reduce the running time of many linear programming–based approximation algorithms from O(n3) to at most O(n2). Moreover, this method can actually be formulated in an equivalent form, called the local ratio method, which does not require the knowledge of the theory of linear programming. In this chapter, we study these two techniques and their relationship.
Ding-Zhu Du, Ker-I Ko, Xiaodong Hu

9. Semidefinite Programming

Abstract
Semidefinite programming studies optimization problems with a linear objective function over semidefinite constraints. It shares many interesting properties with linear programming. In particular, a semidefinite program can be solved in polynomial time. Moreover, an integer quadratic programcan be transformed into a semidefinite programthrough relaxation. Therefore, if a combinatorial optimization problem can be formulated as an integer quadratic program, then we can approximate it using the semidefinite programming relaxation and other related techniques such as the primal’dual schema. As the semidefinite programming relaxation is a higher-order relaxation, it often produces better results than the linear programming relaxation, even if the underlying problem can be formulated as an integer linear program. In this chapter, we introduce the fundamental concepts of semidefinite programming, and demonstrate its application to the approximation of NP-hard combinatorial optimization problems, with various rounding techniques.
Ding-Zhu Du, Ker-I Ko, Xiaodong Hu

10. Inapproximability

Abstract
In this chapter, we turn our attention to a different issue about approximation algorithms. We study how to prove inapproximability results for some NP-hard optimization problems. We are not looking here for a lower bound for the performance ratio of a specific approximation algorithm, but, instead, we try to find a lower bound for the performance ratio of any approximation algorithmfor a given problem.Most results in this study are based on advanced developments in computational complexity theory, which is beyond the scope of this book. Therefore, we limit ourselves to fundamental concepts and results, often with proofs omitted, which are sufficient to establish the inapproximability of many combinatorial optimization problems.
Ding-Zhu Du, Ker-I Ko, Xiaodong Hu

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise