Approximation of the quadratic set covering problem

DOI10.1016/J.DISOPT.2007.10.001MaRDI QIDQ2427697zbMATH OpenOpenAlexFDO

Authors Peter L. Hammer, Bruno Escoffier

Publication date 14 May 2008

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2007.10.001

zbMATH Keywords

approximation algorithmslogical analysis of dataquadratic set covering

Mathematics Subject Classification ID

Boolean programming (90C09)

Recommendations

• scientific article; zbMATH DE number 784428
• Publication:4864343
• scientific article; zbMATH DE number 2081030
• On the facial structure of the set covering polytope
• A generalization of the weighted set covering problem

Cites work

• scientific article; zbMATH DE number 4164874 (Why is no real title available?)
• scientific article; zbMATH DE number 3677572 (Why is no real title available?)
• scientific article; zbMATH DE number 1263202 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 1833397 (Why is no real title available?)
• scientific article; zbMATH DE number 915574 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A new multilayered {PCP} and the hardness of hypergraph vertex cover
• A threshold of ln n for approximating set cover
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for combinatorial problems
• Computationally Related Problems
• On the ratio of optimal integral and fractional covers
• Quadratic programming is in NP
• Some simplified NP-complete graph problems
• The approximability of constraint satisfaction problems
• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems

Cited in

(8)

• Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
• Approximation of the clustered set covering problem
• Relation between set partitioning and set covering problems with quadratic fractional objective functions
• scientific article; zbMATH DE number 845765 (Why is no real title available?)
• A Branch-and-Bound Algorithm for Team Formation on Social Networks
• On a linearization technique for solving the quadratic set covering problem and variations
• Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems
• Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations

This page was built for publication: Approximation of the quadratic set covering problem

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