New hardness results for congestion minimization and machine scheduling
From MaRDI portal
Publication:5901072
DOI10.1145/1007352.1007364zbMath1192.90254MaRDI QIDQ5901072
Joseph (Seffi) Naor, Julia Chuzhoy
Publication date: 15 August 2010
Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1007352.1007364
90C60: Abstract computational complexity for mathematical programming problems
90B35: Deterministic scheduling theory in operations research
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Flows on few paths: Algorithms and lower bounds, A lookahead partitioning heuristic for a new assignment and scheduling problem in a distribution system, A fast heuristic algorithm for the maximum concurrent \(k\)-splittable flow problem, An exact approach for the maximum concurrent \(k\)-splittable flow problem, On the approximation of the single source \(k\)-splittable flow problem, Interval scheduling: A survey