New hardness results for congestion minimization and machine scheduling

DOI10.1145/1183907.1183908MaRDI QIDQ5899540zbMATH OpenOpenAlexFDO

Authors Julia Chuzhoy, Joseph (Seffi) Naor

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

congestion minimizationhardness of approximationnetwork routingresource minimizationscheduling

Mathematics Subject Classification ID

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

Recommendations

• New hardness results for congestion minimization and machine scheduling
• Logarithmic hardness of the directed congestion minimization problem
• Almost-tight hardness of directed congestion minimization
• Hardness of the Undirected Congestion Minimization Problem
• Hardness of the undirected congestion minimization problem

Cited in

(7)

• Logarithmic hardness of the directed congestion minimization problem
• Almost-tight hardness of directed congestion minimization
• Improving fleet utilization for carriers by interval scheduling
• New hardness results for congestion minimization and machine scheduling
• scientific article; zbMATH DE number 7765369 (Why is no real title available?)
• Approximations for Throughput Maximization
• The minimum clique routing problem on cycles

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5899540)