Separation between estimation and approximation

DOI10.1145/2688073.2688101MaRDI QIDQ2989040zbMATH OpenOpenAlexFDO

Authors Shlomo Jozeph, Uriel Feige

Publication date 19 May 2017

Published in Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

integrality gaplinear programmingroundingTFNP

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On estimation algorithms vs approximation algorithms
• The complexity of approximating a nonlinear program
• New class of 0-1 integer programs with tight approximation via linear relaxations
• Proving integrality gaps without knowing the linear program
• Approximate Constraint Satisfaction Requires Large LP Relaxations

Cited in

(2)

• Almost-smooth histograms and sliding-window graph algorithms
• On estimation algorithms vs approximation algorithms

This page was built for publication: Separation between estimation and approximation

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