Improved worst-case complexity for the MIN 3-SET COVERING problem

DOI10.1016/J.ORL.2006.02.004MaRDI QIDQ2643796zbMATH OpenOpenAlexFDO

Authors Vangelis Th. Paschos, F. Della Croce, Bruno Escoffier

Publication date 27 August 2007

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://basepub.dauphine.fr/handle/123456789/2121

zbMATH Keywords

exact algorithmworst-case complexityMIN SET COVERING

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Recommendations

• A modified greedy heuristic for the set covering problem with improved worst case bound
• Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
• A new worst-case bound of heuristic for set covering problem
• An O(m n) algorithm for regular set-covering problems
• scientific article; zbMATH DE number 2102648

Cites work

• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 3803174 (Why is no real title available?)
• 3-coloring in time
• A note on the complexity of minimum dominating set
• Algorithms and Computation
• Automata, Languages and Programming
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Pathwidth of cubic graphs and exact algorithms

Cited in

(5)

• Set multi-covering via inclusion-exclusion
• Algorithms and Computation
• scientific article; zbMATH DE number 7650076 (Why is no real title available?)
• Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom

This page was built for publication: Improved worst-case complexity for the MIN 3-SET COVERING problem

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