New hardness results for congestion minimization and machine schedulingNew hardness results for congestion minimization and machine scheduling

Access Restriction
Subscribed

 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

Source: ACM Digital Library