Access Restriction

Author Chuzhoy, Julia ♦ Naor, Joseph Seffi
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2006
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Hardness of approximation ♦ Congestion minimization ♦ Network routing ♦ Resource minimization ♦ Scheduling
Abstract We study the approximability of two natural NP-hard problems. The first problem is congestion minimization in directed networks. In this problem, we are given a directed graph and a set of source-sink pairs. The goal is to route all the pairs with minimum congestion on the network edges. The second problem is machine scheduling, where we are given a set of jobs, and for each job, there is a list of intervals on which it can be scheduled. The goal is to find the smallest number of machines on which all jobs can be scheduled such that no two jobs overlap in their execution on any machine. Both problems are known to be $\textit{O}(log$ $\textit{n}/log$ log $\textit{n})-approximable$ via the randomized rounding technique of Raghavan and Thompson [1987]. However, until recently, only Max SNP hardness was known for each problem. We make progress in closing this gap by showing that both problems are Ω(log log $\textit{n})-hard$ to approximate unless NP ⊆ $DTIME(\textit{n}\textit{O}(log$ log log $\textit{n})).$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2006-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 53
Issue Number 5
Page Count 15
Starting Page 707
Ending Page 721

Open content in new tab

   Open content in new tab
Source: ACM Digital Library