A note on the set union knapsack problem

DOI10.1016/J.DAM.2013.12.015MaRDI QIDQ2449074zbMATH OpenOpenAlexFDO

Authors Ashwin Arulselvan

Publication date 6 May 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.12.015

zbMATH Keywords

approximationdensest \(k\)-subgraphgreedyset-union knapsack

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Approximation algorithms (68W25) Integer programming (90C10)

Recommendations

• The budgeted maximum coverage problem
• scientific article; zbMATH DE number 698819
• Approximating the dense set-cover problem
• scientific article; zbMATH DE number 1323125
• A Tight Analysis of the Greedy Algorithm for Set Cover

Cites work

• Graph expansion and the unique games conjecture
• scientific article; zbMATH DE number 698819 (Why is no real title available?)
• The budgeted maximum coverage problem
• The dense \(k\)-subgraph problem

Cited in

(6)

• Approximations for restrictions of the budgeted and generalized maximum coverage problems
• The incremental connected facility location problem
• scientific article; zbMATH DE number 936863 (Why is no real title available?)
• Approximation algorithms for maximum weight k-coverings of graphs by packings
• Coordinating monetary contributions in participatory budgeting
• Domination and coverage problems under vulnerability constraints

This page was built for publication: A note on the set union knapsack problem

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