Approximation Algorithms for Network Design Problems

You are cordially invited to attend the PhD Dissertation Defense of Sumedha UNIYAL on Wednesday, October 11th 2017 at 14h00 in room 250 (Main building)

Abstract:
There are lots of natural real-life problems that can be modelled as discrete optimization problems. Unfortunately, many of them are hard to solve efficiently. An approximation algorithm is one of the ways of tackling these hard optimization problems which cannot be solved exactly in polynomial time unless P = NP. These algorithms guarantee a near optimal solution whose value is within a proven factor of the optimal solution value and run in polynomial time. The field of approximation algorithms has grown rapidly over the last few decades, and many techniques have been developed to tackle hard optimization problems. But there are many problems for which a lot of progress is still needed.

In this thesis, we explore the use of two class of techniques, namely LP-based techniques and dynamic programming based techniques to get better approximation algorithms for a number of network design problems. We use the randomized dependent rounding technique inside the relatively new round-or-separate framework (used for dealing with not solvable exponential sized LP’s) to tackle the notorious Uniform Capacitated k-Median problem to get a constant factor approximation algorithm under a capacity violation of 1 + ε factor. For the Unsplittable Flow on a Path (UFP) problem with Bag Constraints, we use randomized LP rounding technique to improve upon the best-known approximation ratio from O(log n) to O(log n/ log log n). For the uniform weight case, we present the first O(1) approximation algorithm. For achieving both these results we use a refined LP relaxation. In addition to that, we also introduce a special case for this problem called the UFP problem with Time Windows for which we present a QP- TAS using a dynamic programming based randomized dissection technique. We also present some interesting constant factor approximation algorithms for Maximizing Monotone Submodular Functions subject to Mixed Covering and Packing Constraints, using a novel dynamic programming based greedy approach. We believe that this technique may be of independent interest as a new technique which has the potential to handle other problems with additional complex constraints where the basic variants (with simple constraints) can be tackled by a greedy approach. One of these algorithms also implies a non-trivial approximation algorithm for the Non-Uniform Capacitated k-Median problem under a special two-distance metric, which was the initial motivation behind studying this problem. Further, we also describe various variants of the Edge Installation Problem (EIP), for which we improve the known approximation algorithms using a different technique, namely randomized rounding with aggregation.

Dissertation Committee:

• Fabrizio Grandoni, IDSIA-Dalle Molle Institute for Artificial Intelligence, Switzerland (Research Advisor)
• Luca Maria Gambardella, IDSIA-Dalle Molle Institute for Artificial Intelligence, Switzerland (Research co-Advisor)
• Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Internal Member)
• Stefan Wolf, Università della Svizzera italiana, Switzerland (Internal Member)
• Naveen Garg, IIT Delhi, India (External Member)
• Stefano Leonardi, Sapienza University of Rome, Italy (External Member)