On the inapproximability of maximum intersection problems

DOI10.1016/j.ipl.2012.06.014zbMath1248.68224OpenAlexW2114146314MaRDI QIDQ456103

Ming-Chuan Yang, Shi-Chun Tsai, Min-Zheng Shieh

Publication date: 23 October 2012

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

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

zbMATH Keywords

approximation algorithmtheory of computationinapproximabilitydisclosure controlmaximum intersection

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

Election Manipulation on Social Networks: Seeding, Edge Removal, Edge Addition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on a maximum \(k\)-subset intersection problem
• Anonymizing binary and small tables is hard to approximate
• The maximum edge biclique problem is NP-complete
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• The budgeted maximum coverage problem
• Approximating min sum set cover
• Maximum subset intersection
• Approximation algorithms for partial covering problems
• Some optimal inapproximability results