New hardness results for congestion minimization and machine scheduling

DOI10.1145/1007352.1007364zbMath1192.90254OpenAlexW2025470209MaRDI 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

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (6)

A fast heuristic algorithm for the maximum concurrent \(k\)-splittable flow problem ⋮ A lookahead partitioning heuristic for a new assignment and scheduling problem in a distribution system ⋮ Interval scheduling: A survey ⋮ An exact approach for the maximum concurrent \(k\)-splittable flow problem ⋮ On the approximation of the single source \(k\)-splittable flow problem ⋮ Flows on few paths: Algorithms and lower bounds

This page was built for publication: New hardness results for congestion minimization and machine scheduling