Approximation of the quadratic set covering problem

DOI10.1016/J.DISOPT.2007.10.001zbMATH Open1157.90484OpenAlexW2140181883MaRDI QIDQ2427697FDOQ2427697

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

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

zbMATH Keywords

approximation algorithmslogical analysis of dataquadratic set covering

Mathematics Subject Classification ID

Boolean programming (90C09)

Cites Work

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

Cited In (8)

• Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
• Approximation of the clustered set covering problem
• Title not available (Why is that?)
• Relation between set partitioning and set covering problems with quadratic fractional objective functions
• 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)