On Approximate Solutions for Combinatorial Optimization Problems
From MaRDI portal
Publication:3477970
DOI10.1137/0403025zbMath0699.68077OpenAlexW2024380444MaRDI QIDQ3477970
Publication date: 1990
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0403025
partitioningcoveringcombinatorial optimizationautomatagraph coloringNP-completenessindependent setreductionsset packingapproximation algorithmsconsistent
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (27)
Property testing of the Boolean and binary rank ⋮ Chromatic characterization of biclique covers ⋮ Computational aspects of the 2-dimension of partially ordered sets ⋮ On an approximation measure founded on the links between optimization and polynomial approximation theory ⋮ Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms ⋮ An approximation algorithm for state minimization in 2-MDFAs ⋮ Improved approximations for maximum independent set via approximation chains ⋮ Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa ⋮ Time slot scheduling of compatible jobs ⋮ Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms ⋮ Sparsification and subexponential approximation ⋮ A survey on the structure of approximation classes ⋮ The approximation of maximum subgraph problems ⋮ Finding approximate solutions to NP-hard problems by neural networks is hard ⋮ Approximate solution of NP optimization problems ⋮ Greed is good: Approximating independent sets in sparse and bounded-degree graphs ⋮ A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem ⋮ The 0-1 inverse maximum stable set problem ⋮ Structure of polynomial-time approximation ⋮ Reductions, completeness and the hardness of approximability ⋮ On the probabilistic minimum coloring and minimum \(k\)-coloring ⋮ Probabilistic graph-coloring in bipartite and split graphs ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ Differential approximation algorithms for some combinatorial optimization problems ⋮ Efficient approximation for restricted biclique cover problems ⋮ On subexponential and FPT-time inapproximability ⋮ On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.
This page was built for publication: On Approximate Solutions for Combinatorial Optimization Problems
