Approximation Algorithms For Resource Allocation And Network Problems

Decanato - Facoltà di scienze informatiche

Data d'inizio: 19 Dicembre 2013

Data di fine: 20 Dicembre 2013

You are cordially invited to attend the PhD Dissertation Defense of Georgios STAMOULIS on Thursday, December 19th 2013 at 9h00 in SI-006

Numerous practical problems are integer optimization problems that are intractable which means that one need to settle for an approximate solution if the time available to perform the computation is limited. In this thesis we address a number of such intractable problems, and we prove polynomial time approximation guarantees.

More specifically, we show how linear programming techniques help us design good approximation algorithms (actually a \textit{family} of algorithms) for a generalization of the \textit{maximum matching problem}. Such generalizations, beside of the theoretical interest, have numerous applications especially in the modern technology of optical networking systems. We show how the linear programming formulation of the problem has certain nice properties that we can take advantage of and design good approximation algorithms. We then move into the study of a special case of a specific and notoriously hard resource allocation problem. We show how a structural characterization of optimal solution can help us in retrieving almost optimal assignments. This leads to a combinatorial PTAS for the problem of our interest. Finally, we address a problem of a slightly different flavor: we show how, for the more practical and more realistic \textit{On-Line} scenario for a host of well known and well studied scheduling problems, we can obtain a family of algorithms for approximating the \textit{optimal}-competitive ratio (the on-line analogue of the approximation factor). Our techniques are based on a reduction step where we show that with minimal loss we can reduce the infinite space of possible outcomes to a finite one, and then an enumeration step where we enumerate all these finitely many outcomes and output the one that serves our purposes.

Dissertation Committee:

  • Prof. Luca Maria Gambardella, IDSIA, Switzerland (Research advisor)
  • Prof. Monaldo Mastrolilli, IDSIA, Switzerland (Research co-advisor)
  • Prof. Michele Parrinello, Università della Svizzera italiana, Lugano, Switzerland, (Internal Member)
  • Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Lugano, Switzerland, (Internal Member)
  • Prof. Christoph Durr, Universite Pierre et Marie Curie-LIP6, Paris, France, (External Member)
  • Prof. Aris Pagourtzis, National Technical University of Athens, Athens, Hellas. (External Member)