A dynamic edge covering and scheduling problem: complexity results and approximation algorithms

DOI10.1007/S11590-013-0658-XMaRDI QIDQ2448193zbMATH OpenOpenAlexFDO

Authors Jiaming Qiu, Thomas C. Sharkey

Publication date 30 April 2014

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-013-0658-x

zbMATH Keywords

approximation algorithmscomplexityendpoint coveringscheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Integer programming (90C10) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A combination of parallel machine scheduling and the covering problem
• Combination of parallel machine scheduling and vertex cover
• Infinite product exponents for modular forms
• Approximation algorithms for min-max path cover problems with service handling time
• Task scheduling in networks

Cites work

• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• An Application of Bin-Packing to Multiprocessor Scheduling
• Approximation algorithms for maximization problems arising in graph partitioning
• Bounds on Multiprocessing Timing Anomalies
• Complexity of finding dense subgraphs
• Greedily Finding a Dense Subgraph
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Scheduling. Theory, algorithms, and systems.
• The dense \(k\)-subgraph problem
• Tighter Bounds for the Multifit Processor Scheduling Algorithm

Cited in

(1)

• Edge finding for cumulative scheduling

This page was built for publication: A dynamic edge covering and scheduling problem: complexity results and approximation algorithms

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