Separation between Estimation and Approximation

Channel:
Microsoft Research
Subscribers:
342,000
Published on ● Video Link: https://www.youtube.com/watch?v=6qSXeW71aCk


Duration: 1:02:28
558 views
2

We show (under standard assumptions) that there are NP optimization problems for which estimation is easier than approximation. Namely, one can estimate the value of the optimal solution within a ratio of r, but it is difficult to find a solution whose value is within r of optimal. As an important special case, we show that there are linear programming relaxations for which no polynomial time rounding technique matches the integrality gap of the linear program. Joint work with Shlomo Jozeph.



Other Videos By Microsoft Research


2016-06-21Social Media Platforms and the Curation of Public Culture
2016-06-21Context-aware programming languages
2016-06-21Supporting Proxemic Interactions with Multi-Scale Electric Field Sensing
2016-06-21Tsunami or Sea Change? Responding to the Explosion of Student Interest in Computer Science
2016-06-21IEEE Power Engineering Society
2016-06-21Cutting tail latency in cloud data stores via adaptive replica selection
2016-06-21Discursis: A Computational Methodology for the Analysis of Communication Data
2016-06-21Change Dyslexia: Early Detection and Intervention at Large Scale
2016-06-21Contextualised interaction in and with our environment
2016-06-21Big Data and Bayesian Nonparametrics
2016-06-21Separation between Estimation and Approximation
2016-06-21Information Geometry
2016-06-21Data Visualization, Transformation and Feature Selection
2016-06-21From Data to Stories: What Making a Billion Charts Has Taught Me about the World
2016-06-21Controlled Data Sharing for Collaborative Predictive Blacklisting
2016-06-21Stuff machine learning, let’s talk about climate change.
2016-06-21Computer Vision and Intelligent Services
2016-06-21ChronoZoom Prototype for Museums
2016-06-21Data Science Summer School 2015- The Cost of Public School
2016-06-21Computer Vision: New and Renewed Opportunities
2016-06-21Compositional Models


Tags:
microsoft research
deep learning