Confronting hardness using a hybrid approach

DOI10.1145/1109557.1109558zbMath1192.68381OpenAlexW4252095493MaRDI QIDQ3581485

Shan Leung Maverick Woo, Virginia Vassilevska Williams, R. Ryan Williams

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Algorithm portfolios for noisy optimization ⋮ Improved Parameterized Algorithms for above Average Constraint Satisfaction ⋮ Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Parameterized approximation via fidelity preserving transformations ⋮ Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ Exponential-time approximation of weighted set cover ⋮ Structural Properties of Hard Metric TSP Inputs ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms ⋮ An Exponential Time 2-Approximation Algorithm for Bandwidth

This page was built for publication: Confronting hardness using a hybrid approach