On Approximate Solutions for Combinatorial Optimization Problems

DOI10.1137/0403025zbMATH Open0699.68077OpenAlexW2024380444MaRDI QIDQ3477970FDOQ3477970

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

Recommendations

scientific article; zbMATH DE number 780787
scientific article; zbMATH DE number 1789921
scientific article; zbMATH DE number 3873084
Computational combinatorial optimization. Optimal of probably near-optimal solutions
Approximability of hard combinatorial optimization problems: an introduction
scientific article; zbMATH DE number 3873085
Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
Approximation algorithms for stochastic combinatorial optimization problems
Differential approximation algorithms for some combinatorial optimization problems

combinatorial optimization approximation algorithms graph coloring NP-completeness automata covering independent set reductions partitioning set packing consistent

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (40)

Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
Property testing of the Boolean and binary rank
On simple combinatorial optimization problems. A collection of contributions in honour of Jack van Lint
Optimal schemes for combinatorial query problems with integer feedback
Finding approximate solutions to NP-hard problems by neural networks is hard
Title not available (Why is that?)
Efficient approximation for restricted biclique cover problems
Chromatic characterization of biclique covers
Continuous reductions among combinatorial optimization problems
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
An approximation algorithm for state minimization in 2-MDFAs
Ultimate greedy approximation of independent sets in subcubic graphs
Title not available (Why is that?)
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
Differential approximation algorithms for some combinatorial optimization problems
Greed is good: Approximating independent sets in sparse and bounded-degree graphs
Improved approximations for maximum independent set via approximation chains
On an approximation measure founded on the links between optimization and polynomial approximation theory
Probabilistic graph-coloring in bipartite and split graphs
Approximate solution of NP optimization problems
Approximative solutions of best choice problems
A survey on the structure of approximation classes
Time slot scheduling of compatible jobs
Title not available (Why is that?)
On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.
A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
The 0-1 inverse maximum stable set problem
The approximation of maximum subgraph problems
Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
Computational aspects of the 2-dimension of partially ordered sets
Combinatorial optimization with interaction costs: complexity and solvable cases
On the probabilistic minimum coloring and minimum \(k\)-coloring
Title not available (Why is that?)
A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
Sparsification and subexponential approximation
Structure of polynomial-time approximation
A portable and scalable algorithm for a class of constrained combinatorial optimization problems
Reductions, completeness and the hardness of approximability

This page was built for publication: On Approximate Solutions for Combinatorial Optimization Problems

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