טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentKutiel Gilad
SubjectApproximation Algorithms for Submodular Maximization
and Network Design Problems
DepartmentDepartment of Computer Science
Supervisors Dr. Roy Schwartz
Dr. Dror Rawitz


Abstract

In this thesis we develop and analyze approximation algorithms, while focusing on two families of problems: network design and submodular optimization.

For the former family we consider the problems of Convex Recoloring and the Service Chain Placement in SDNs.

For the latter family we consider the problems of maximizing a monotone submodular function given a knapsack constraint and the Maximum Carpool Matching problem.


In a typical instance of a network design problem we are given a collection of resources and our goal is to construct a desired network that satisfies some requirements while utilizing the minimum possible amount of resources.


In the Convex Recoloring problem, we are given a set C and a coloring of an undirected graph, G(V, E), is a function x:V -> C.

We say that a coloring is convex if the vertices of each color induce a connected graph of  G.

The goal is to find a convex coloring of the graph that recolors the minimum number of vertices.

In this thesis we consider a special case of this problem, namely the 2-Convex Recoloring problem, in which the original coloring uses each color in C to color at most two vertices.

For this special case we develop a greedy 3/2-approximation algorithm.

We show that if the input graph is a path then this is in fact a 5/4-approximation algorithm.


In the Service Chain Placement in SDNs problem our goal is to find an optimal resource allocation in a software defined networks that support network function virtualization.

We model the problem and give a fully polynomial time approximation scheme for the special case where the physical network is a directed acyclic graph.

For general graphs we give a parameterized algorithm.

This algorithm finds an optimal solution efficiently for cactus network.


Submodularity is a fundamental mathematical notion that captures the concept of economy of scale and is prevalent in many areas of science and technology.

Given a ground set U a set function f:2^U -> R over U is called submodular if it has the diminishing returns property:

f(A \cup {a}) - f(A) >= f(B \cup a) - f(B) for every A \subseteq B \subseteq U and a \in U \ B.

Submodular functions naturally arise in different disciplines such as combinatorics, graph theory, probability, game theory, and economics.


In this thesis we consider the problem of maximizing a monotone, submodular function given a Knapsack constraint and develop a fast and simple approximation algorithm for this problem.

We also consider the Maximum Carpool Matching problem, where we seek to find an optimal way in which a group of people should share their ride.

We show that this problem can be formalized as a non-monotone, unconstrained, submodular function maximization, thus admits a 1/2-approximation.