The (Im)possibility of simple search-to-decision reductions for approximation problems

DOI10.4230/LIPICS.APPROX/RANDOM.2023.10MaRDI QIDQ6663019zbMATH OpenFDO

Authors Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

Publication date 14 January 2025

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2023.10

zbMATH Keywords

constraint satisfactiondiscrete optimizationoraclessearch-to-decision reductionstraveling salesman

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

This page was built for publication: The (Im)possibility of simple search-to-decision reductions for approximation problems

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