Inapproximability results for bounded variants of optimization problems.

DOI10.1007/B11926MaRDI QIDQ5900783zbMATH OpenOpenAlexFDO

Authors Miroslav Chlebík, Janka Chlebíková

Publication date 20 April 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b11926

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27)

Recommendations

• Complexity of approximating bounded variants of optimization problems
• Non-approximability results for optimization problems on bounded degree instances
• scientific article; zbMATH DE number 2011853
• On approximation properties of the Independent set problem for degree 3 graphs
• Approximation hardness of dominating set problems in bounded degree graphs

Cited in

(23)

• On the approximability of the maximum induced matching problem
• On the complexity of computing the temporal hybridization number for two phylogenies
• Approximating Nash social welfare under binary XOS and binary subadditive valuations
• Complexity of approximating bounded variants of optimization problems
• Hardness and approximation results for packing Steiner trees
• Approximation hardness of edge dominating set problems
• Approximation and inapproximability results for maximum clique of disc graphs in high dimensions
• Packing triangles in low degree graphs and indifference graphs
• Using VNS for the optimal synthesis of the communication tree in wireless sensor networks
• Optimizing budget allocation for center and median points
• Inapproximability of vertex cover and independent set in bounded degree graphs
• On the hardness of range assignment problems
• On the approximability and hardness of minimum topic connected overlay and its special instances
• scientific article; zbMATH DE number 2011853 (Why is no real title available?)
• scientific article; zbMATH DE number 2086657 (Why is no real title available?)
• scientific article; zbMATH DE number 1839429 (Why is no real title available?)
• Non-approximability results for optimization problems on bounded degree instances
• On the complexity of approximating \(k\)-dimensional matching
• Ultimate greedy approximation of independent sets in subcubic graphs
• On the complexity of finding 1-center spanning trees
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Simultaneous matchings: Hardness and approximation
• Commitment under uncertainty: Two-stage stochastic matching problems

This page was built for publication: Inapproximability results for bounded variants of optimization problems.

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