Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP

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


Duration: 55:47
1,403 views
14

We study the prize-collecting versions of the Steiner tree, traveling salesman, and stroll (a.k.a. PATH-TSP) problems (PCST, PCTSP, and PCS, respectively): given a graph (V,E) with costs on each edge and a penalty (a.k.a. prize) on each node, the goal is to find a tree (for PCST), cycle (for PCTSP), or stroll (for PCS) that minimizes the sum of the edge costs in the tree/cycle/stroll and the penalties of the nodes not spanned by it. In addition to being a useful theoretical tool for helping to solve other optimization problems, PCST has been applied fruitfully by AT&T to the optimization of real-world telecommunications networks. The most recent improvements for the first two problems, giving a 2-approximation algorithm for each, appeared first in 1992. (A 2-approximation for PCS appeared in 2003.) The natural linear programming (LP) relaxation of PCST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present (2 - epsilon)-approximation algorithms for all three problems, connected by a unified technique for improving prize collecting algorithms that allows us to circumvent the integrality gap barrier.



Other Videos By Microsoft Research


2016-09-07Artificial Companions as dialogue agents
2016-09-07Disciplined Message Passing
2016-09-07The Recognition of Engagement in Human-Robot Dialogs
2016-09-07Of Scripts and Programs: Tall tales, Urban Legends, and Future Prospects
2016-09-07Who 'Dat? Identity resolution in large email collections
2016-09-07Designing for Urban Green Space
2016-09-07Rethink: A Business Manifesto for Cutting Costs and Boosting Innovation
2016-09-07Music Understanding: Research and Applications
2016-09-07A New Era of Resource Responsibility for Sensor Networks
2016-09-07A Dynamic Bayesian Network Click Model for Web Search Ranking
2016-09-07Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
2016-09-07The Elements: A Visual Exploration of Every Known Atom in the Universe
2016-09-07eScience 2009 Tutorial: Trident - A Scientific Workbench
2016-09-07The Microsoft Biology Initiative: An Open Source Framework and Toolset for Bioinformatics Research
2016-09-07Keynote - From Flops to Petabytes: the Expanding Role of Data in NSF Cyberinfrastructure
2016-09-072009 eScience: How optimized Environmental Sensing Helps Address Information Overload on the Web
2016-09-072009 eScience: Beyond Sensors: Curating Ancillary Data for Carbon-Climate Science
2016-09-072009 eScience: Healthcare e-Labs: Opening and Integrating Models of Health
2016-09-07The Fourth Paradigm - Realizing Jim GrayΓÇÖs Vision for Data-Intensive Scientific Discovery
2016-09-072009 eScience: Extracting Natural Laws from Data: Invariants are better than predictive models
2016-09-07Incorporating Problem-based Learning in Medical Image Processing


Tags:
microsoft research