On the inapproximability of maximum intersection problems

DOI10.1016/J.IPL.2012.06.014zbMATH Open1248.68224OpenAlexW2114146314MaRDI QIDQ456103FDOQ456103

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

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

Recommendations

• Maximum subset intersection
• 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 1839479

zbMATH Keywords

approximation algorithminapproximabilitytheory of computationdisclosure controlmaximum intersection

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A course in combinatorics.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Approximation algorithms for partial covering problems
• Some optimal inapproximability results
• Title not available (Why is that?)
• The budgeted maximum coverage problem
• Title not available (Why is that?)
• The maximum edge biclique problem is NP-complete
• Anonymizing binary and small tables is hard to approximate
• Approximating min sum set cover
• Maximum subset intersection
• A note on a maximum \(k\)-subset intersection problem

Cited In (7)

• Inapproximability of finding maximum hidden sets on polygons and terrains
• A note on a maximum \(k\)-subset intersection problem
• Approximation hardness of optimization problems in intersection graphs of \(d\)-dimensional boxes
• Title not available (Why is that?)
• Election manipulation on social networks: seeding, edge removal, edge addition
• Maximum subset intersection
• Title not available (Why is that?)

This page was built for publication: On the inapproximability of maximum intersection problems

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