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

DOI10.1007/s00453-022-00964-6OpenAlexW4286425593MaRDI QIDQ2161003

Marilena Leichter, Marinus Gottschau

Publication date: 3 August 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsmaintenance schedulinghitting set

Mathematics Subject Classification ID

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

Cites Work

• A model for minimizing active processor time
• On the minimum hitting set of bundles problem
• Efficient bounds for the stable set, vertex cover and set packing problems
• On dependent randomized rounding algorithms
• LP rounding and combinatorial algorithms for minimizing active and busy time
• Parameterizations of hitting set of bundles and inverse scope
• Greedy approximations for minimum submodular cover with submodular cost
• Busy time scheduling on a bounded number of machines (extended abstract)
• Minimizing Busy Time in Multiple Machine Real-time Scheduling
• Scheduling Tasks to Minimize Active Time on a Processor with Unlimited Capacity
• Ottimizzazione Combinatoria
• Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
• Reducibility among Combinatorial Problems
• Submodular Function Minimization under Covering Constraints
• Analytical approach to parallel repetition
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

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