Technical Report PHD-2019-05

Title: Approximation Algorithms for Submodular Maximization and Network Design Problems
Authors: Gilad Kutiel
Supervisors: Roy Schwartz, Dror Rawitz
PDFCurrently 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.

CopyrightThe 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 (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2019
To the main CS technical reports page

Computer science department, Technion