New hardness results for congestion minimization and machine scheduling

DOI10.1145/1183907.1183908zbMath1326.68147OpenAlexW1967762975MaRDI QIDQ5899540

Joseph (Seffi) Naor, Julia Chuzhoy

Publication date: 4 December 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1183907.1183908

zbMATH Keywords

schedulingnetwork routinghardness of approximationresource minimizationcongestion minimization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (2)

Improving fleet utilization for carriers by interval scheduling ⋮ Unnamed Item

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