文档介绍：New Hardness Results for Congestion Minimization and Machine Scheduling JULIA CHUZHOY CSAIL MIT and Dept. of CIS, University of Pennsylvania and JOSEPH (SEFFI) puter Science Dept., Technion We study the approximability of two natural NP-hard problems. The ?rst problem iscongestion minimizationin works. 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 work edges. The second problem ismachine scheduling, where we are given a set of jobs, and for each job, there is a list of intervals on which it can be goal is to ?nd 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 beO(logn/loglogn)-approximable via the randomized rounding technique of Raghavan and Thompson. However, until recently, only Max SNP hardness was known for each problem. We make progressin closing this gap by showing that both problems are ?(log logn)-hard to approximate unlessNP?DTIME(n O(log log logn)). Categories and Subject Descriptors: [Discrete Mathematics]: Graph work problems; [Analysis of Algorithms and plexity]: Nonnumerical Algo- rithms and putations on discrete structures General Terms: Theory Additional Key Words and Phrases: Hardness of approximation, congestion minimization, network routing, scheduling, resource minimization 1. INTRODUCTION In this paper we study the approximability of the congestionminimization and the machine scheduling problems. Both these problems deal with resource min- imization, though in di?erent contexts: congestion minimization aims at routing source-sink pairs in work, so as to minimize edge congestion, while in the ma- chine scheduling problemthe goal is to schedule jobs on machines, while minimizing the number of machines used. Congestion minimization and machine scheduling are probably the most natural resource minimization problems