Combinatorial dominance guarantees for problems with infeasible solutions

DOI10.1145/1435375.1435383zbMath1445.68105OpenAlexW1978936478MaRDI QIDQ4962766

Yochai Twitto, Daniel Berend, Steven S. Skiena

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1435375.1435383

zbMATH Keywords

computational complexityapproximation algorithmsalgorithm analysisdominance analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (2)

Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms ⋮ A domination algorithm for {0,1}-instances of the travelling salesman problem

This page was built for publication: Combinatorial dominance guarantees for problems with infeasible solutions