Deeparnab Chakrabarty Defense Dissertation

Most combinatorial optimization problems are NP-hard, which imply that under well-believed complexity assumptions, there exist no polynomial time algorithms to solve them. To cope with the NP-hardness, approximation algorithms which return solutions close to the optimal, have become a rich field of study. One successful method for designing approximation algorithms has been to model the optimization problem as an integer program and then using its polynomial time solvable linear programming relaxation for the design and analysis of such algorithms. Such a technique is called the LP-based technique.

In this thesis, we study the algorithmic aspects of three classes of combinatorial optimization problems using LP-based techniques as our main tool.

• Connectivity Problems: We study the Steiner tree problem and devise new linear programming relaxations for the problem. We show an equivalence of our relaxation with the well studied bidirected cut relaxation for the Steiner tree problem. Furthermore, for a class of graphs called quasi-bipartite graphs, we improve the best known upper bound on the integrality gap from 3/2 to 4/3. Algorithmically, we obtain fast and simple approximation algorithms for the Steiner tree problem on quasi-bipartite graphs.
• Allocation Problems: We study the budgeted al location problem of allocating a set of indivisible items to a set of agents who bid on it but possess a hard budget constraint more than which they are unwilling to pay. This problem is a special case of submodular welfare maximization. We use a natural LP relaxation for the problem and improve the best known approximation factor for the problem from ~ 0.632 to 3/4. We also improve the inapproximability factor of the problem to 15/16 and use our techniques to show inapproximability results for many other allocation problems. We also study online allocation problems where the set of items are unknown and appear one at a time. Under some necessary assumptions we provide online algorithms for many problems which attain the (almost) optimal competitive ratio. Both these works have the sponsored search auctions hosted by search engines on the Internet.
• Design Problems: We formally define and study design problems which asks how the weights of an input instance can be designed, so that the minimum (or maximum) of a certain function of the input can be maximized (respectively, minimized). We show if the function can be approximated to any factor α, then the optimum design can be approximated to the same factor. We also show that (max-min) design problems are dual to packing problems. We use the framework developed by our study of design problems to obtain results about fractionally packing Steiner trees in a "black-box" fashion. Finally, we study integral packing of spanning trees and provide an alternate proof of a theorem of Nash-Williams and Tutte about packing spanning trees.