Ph.D Thesis

Ph.D StudentChuzhoy Julia
SubjectHardness of Approximation and New Approximability Classes
DepartmentDepartment of Computer Science
Supervisor PROF. Joseph Naor


NP-hard problems constitute a class of computational problems, many of which have important applications in science and industry. No efficient algorithms are known for them, and it is conjectured that none exist. Hence, the natural way of dealing with NP-completeness is via approximation. The approximability status of many NP-hard problems still remains open. However, until recently, all the natural NP-hard problems seemed to fall within very few approximation classes, having either constant or logarithmic and higher approximation factor, thus suggesting that no intermediate classes exist.

In this thesis we study the approximability of several fundamental NP-hard problems. Our results imply that the above view of approximation classes is incorrect, as some of the problems we study do not belong to the “conventional” approximation classes.

We start by exploring the approximability of a basic clustering problem called the asymmetric k-center, for which an O(log*n)-approximation is known. We prove a log*n-hardness of approximation, thus resolving the approximability of this fundamental problem. We present two additional problems with unconventional approximation factors: congestion minimization in directed networks and machine scheduling. Congestion minimization is a natural mathematical model for many routing problems in networks. Machine scheduling is a basic problem from a completely different field - job scheduling. Both problems are known to have O(log n/log log n)-approximation, and we show that they are (log log n)-hard to approximate. We proceed to consider the metric labeling problem, for which a logarithmic approximation is known. Metric labeling is a popular mathematical model that abstracts a variety of classification problems. We show that no constant factor approximation exists for this problem. Finally, we provide new hardness results for several popular network design problems.