scientific article; zbMATH DE number 751135

MaRDI QIDQ4764626zbMATH OpenFDO

Authors Viggo Kann

Publication date 4 May 1995

zbMATH Keywords

approximation preserving reductioncompletenessgraph problemsminimization problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Polynomially bounded minimization problems which are hard to approximate
• Strong lower bounds on the approximability of some NPO PB-complete maximization problems
• On the hardness of approximating minimization problems
• On the complexity of approximating the independent set problem

Cited in

(34)

• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• The complexity of makespan minimization for pipeline transportation.
• On approximability of linear ordering and related NP-optimization problems on graphs.
• Some APX-completeness results for cubic graphs
• Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
• Approximability and exact resolution of the multidimensional binary vector assignment problem
• Scheduling on parallel machines with preemption and transportation delays
• Analyzing unit read-once refutations in difference constraint systems
• Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas
• Analyzing the reachability problem in choice networks
• On the analysis of optimization problems in arc-dependent networks
• Minimal distance of propositional models
• Analyzing read-once cutting plane proofs in Horn systems
• On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
• Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems
• Approximating Alternative Solutions
• Strong lower bounds on the approximability of some NPO PB-complete maximization problems
• Kernel bounds for path and cycle problems
• Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
• Minimizer Extraction in Polynomial Optimization Is Robust
• A survey on the structure of approximation classes
• Polynomially bounded minimization problems which are hard to approximate
• Hardness and Approximation Results for L_p-Ball Constrained Homogeneous Polynomial Optimization Problems
• Structure in approximation classes
• On the approximability of path and cycle problems in arc-dependent networks
• Reachability in choice networks
• Optimal length cutting plane refutations of integer programs
• Unit read-once refutations for systems of difference constraints
• Paths, trees and matchings under disjunctive constraints
• Improved approximations of independent dominating set in bounded degree graphs
• A quantum walk-assisted approximate algorithm for bounded NP optimisation problems
• Optimal length cutting plane refutations of integer programs
• An efficient branch-and-bound algorithm for the one-to-many shortest path problem with additional disjunctive conflict constraints
• Finding disjoint paths with related path costs

This page was built for publication:

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