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

DOI10.1016/J.ORL.2006.02.004zbMATH Open1123.68048OpenAlexW2023862676MaRDI QIDQ2643796FDOQ2643796

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 3-coloring in time
• Automata, Languages and Programming
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Algorithms and Computation
• Pathwidth of cubic graphs and exact algorithms
• A note on the complexity of minimum dominating set
• Title not available (Why is that?)

Cited In (5)

• Algorithms and Computation
• Set multi-covering via inclusion-exclusion
• Title not available (Why is that?)
• 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)