Iterative Methods in Combinatorial Optimization

Опубликовано 6 сентября 2016, 18:31

In this talk we will demonstrate iterative methods as a general technique to analyze linear programming formulations of combinatorial optimization problems. We first show an application of the method to the Minimum Bounded Degree Spanning Tree problem. We present a polynomial time algorithm that returns a spanning tree of optimal cost while exceeding the degree bound of any vertex by at most an additive one. This is the best possible result for this problem and settles a 15-year-old conjecture of Goemans affirmatively. We will present a new short proof of the result. We will also discuss extensions to degree constrained versions of more general network design problems and give first additive approximation algorithms using the iterative method. These results add to a rather small list of combinatorial optimization problems which have an additive approximation algorithm. I will also discuss applications of the method to various multi-criteria problems. This talk will contain joint works with Lap Chi Lau, Seffi Naor, Mohammad Salavatipour and R. Ravi when candidates can influence their position, can lead to sub-optimal result and challenges the basic assumption that the candidates arrive in a random order. This issue gains more importance since secretary problem and its variants have been used to design online auctions. In this talk, I will describe a general framework for dealing with the issue of incentives in secretary problems. We formalize an intuitive notion of incentive compatible mechanisms in which the position of the candidate is independent of his chances of being hired. We then construct optimal incentive compatible mechanisms which select the best secretary with high probability. This is joint work with Niv Buchbinder and Kamal Jain.