Minimum hitting set of interval bundles problem: computational complexity and approximability

DOI10.1007/S00453-022-00964-6MaRDI QIDQ2161003zbMATH OpenOpenAlexFDO

Authors Marinus Gottschau, Marilena Leichter

Publication date 3 August 2022

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-022-00964-6

zbMATH Keywords

approximation algorithmshitting setmaintenance scheduling

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Recommendations

• On the minimum hitting set of bundles problem
• On the Minimum Hitting Set of Bundles Problem
• Parameterizations of hitting set of bundles and inverse scope
• Minimum membership hitting sets of axis parallel segments
• An efficient branch-and-bound solver for hitting set

Cites work

• Analytical approach to parallel repetition
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Busy time scheduling on a bounded number of machines (extended abstract)
• Efficient bounds for the stable set, vertex cover and set packing problems
• Greedy approximations for minimum submodular cover with submodular cost
• Inapproximability of hypergraph vertex cover and applications to scheduling problems
• LP rounding and combinatorial algorithms for minimizing active and busy time
• Minimizing busy time in multiple machine real-time scheduling
• On dependent randomized rounding algorithms
• On the minimum hitting set of bundles problem
• Ottimizzazione Combinatoria
• Parameterizations of hitting set of bundles and inverse scope
• Reducibility among combinatorial problems
• Scheduling tasks to minimize active time on a processor with unlimited capacity
• Submodular Function Minimization under Covering Constraints

This page was built for publication: Minimum hitting set of interval bundles problem: computational complexity and approximability

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