Maximum subset intersection

DOI10.1016/J.IPL.2010.12.003MaRDI QIDQ1944892zbMATH OpenOpenAlexFDO

Authors Raphaël Clifford, Alexandru Popa

Publication date 28 March 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.12.003

zbMATH Keywords

approximation algorithmscombinatorial problems

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Approximation algorithms (68W25)

Recommendations

• On the inapproximability of maximum intersection problems
• A note on a maximum \(k\)-subset intersection problem
• An Integer Programming Formulation for the Maximum k-Subset Intersection Problem
• On the complexity of approximating \(k\)-set packing
• scientific article; zbMATH DE number 1670858

Cites work

• scientific article; zbMATH DE number 3495588 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A threshold of ln n for approximating set cover
• Algorithmic construction of sets for k -restrictions
• An approximation algorithm for the fault tolerant metric facility location problem
• Approximating min sum set cover
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for partial covering problems
• Linear degree extractors and the inapproximability of max clique and chromatic number
• The budgeted maximum coverage problem

Cited in

(5)

• scientific article; zbMATH DE number 2217319 (Why is no real title available?)
• Equilibria of plurality voting: lazy and truth-biased voters
• A note on a maximum \(k\)-subset intersection problem
• On the inapproximability of maximum intersection problems
• Applications of random algebraic constructions to hardness of approximation

This page was built for publication: Maximum subset intersection

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