Approximation hardness for small occurrence instances of NP-hard problems

DOI10.1007/3-540-44849-7_21MaRDI QIDQ4437505zbMATH OpenFDO

Authors Miroslav Chlebík, Janka Chlebíková

Publication date 2 December 2003

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2653/26530152.htm, https://figshare.com/articles/presentation/Approximation_hardness_for_small_occurrence_instances_of_NP-hard_problems/23343554

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
• Inapproximability results for bounded variants of optimization problems.
• Non-approximability results for optimization problems on bounded degree instances
• Approximating bounded degree instances of NP-hard problems
• scientific article; zbMATH DE number 2086657

Cited in

(20)

• An improved randomized approximation algorithm for maximum triangle packing
• Improved approximation algorithms for weighted 2-path partitions
• The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics
• Weighted amplifiers and inapproximability results for travelling salesman problem
• Complexity of approximating bounded variants of optimization problems
• Approximation hardness of edge dominating set problems
• Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
• Triangle strings: structures for augmentation of vertex-disjoint triangle sets
• An approximation algorithm for maximum triangle packing
• Improved approximation algorithms for weighted 2-path partitions
• A Problem Kernelization for Graph Packing
• scientific article; zbMATH DE number 7650083 (Why is no real title available?)
• Inapproximability results for bounded variants of optimization problems.
• A randomized approximation algorithm for metric triangle packing
• On the complexity of the cable-trench problem
• A deterministic approximation algorithm for metric triangle packing
• An improved approximation algorithm for metric triangle packing
• Undesignable motifs in structural RNAs and combinatorial consequences
• Participatory budgeting with project groups
• The Steiner tree problem on graphs: inapproximability results

This page was built for publication: Approximation hardness for small occurrence instances of NP-hard problems

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