Technical Report PHD-2019-05

 TR#: PHD-2019-05 Class: PHD Title: Approximation Algorithms for Submodular Maximization and Network Design Problems Authors: Gilad Kutiel Supervisors: Roy Schwartz, Dror Rawitz PDF Currently accessibly only within the Technion network 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 \textsc{Convex Recoloring} and the \textsc{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 \textsc{Maximum Carpool Matching} problem. In a typical instance of a \emph{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 \textsc{Convex Recoloring} problem, we are given a set $\mathcal{C}$ and a \emph{coloring} of an undirected graph, $G(V, E)$, is a function $\chi:V \to \mathcal{C}$. We say that a coloring is \emph{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 \textsc{2-Convex Recoloring} problem, in which the original coloring uses each color in $\mathcal{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 \textsc{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 \to \mathbb{R}_+$ over $U$ is called \emph{submodular} if it has the \emph{diminishing returns} property: $f(A \cup \{a\}) - f(A) \geq f(B \cup \{a\}) - f(B)$ for every $A \subseteq B \subseteq U$ and $a \in U \setminus 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 \textsc{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. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2019/PHD/PHD-2019-05), rather than to the URL of the PDF files directly. The latter URLs may change without notice.