Technical Report PHD-2021-15

Title: Submodular Maximization with Assignment Constraints and Parameterized Approximations
Authors: Ariel Kulik
Supervisors: Hadas Shachnai
PDFCurrently accessibly only within the Technion network
Abstract: In this thesis we study submodular maximization with assignment constraints and parameterized approximations.

One main focus of this research is in the intersection between submodular maximization and resource allocation problems such as Knapsack, Multiple Knapsack and the Generalized Assignment Problem.

Many algorithms for maximizing a monotone submodular function subject to a knapsack constraint rely on a natural greedy heuristic. We present a novel refined analysis of this heuristic which enables us to: (1) reduce the enumeration in the tight $(1-e^{-1})$-approximation of [Sviridenko 04] from subsets of size three to two; (2) present an improved upper bound of $0.42945$ for the classic algorithm which returns the better between a single element and the output of the greedy heuristic.

A multiple knapsack constraint over a set of items is defined by a set of bins of arbitrary capacities, and a weight for each of the items. An assignment for the constraint is an allocation of subsets of items to the bins which adheres to bin capacities. In this work we present a unified algorithm that yields efficient approximations for a wide class of submodular and modular optimization problems involving multiple knapsack constraints. One notable example is a {\em polynomial time approximation scheme} for Multiple-Choice Multiple Knapsack, improving upon the best known ratio of $2$. Another example is Non-monotone Submodular Multiple Knapsack, for which we obtain a $(0.385-\eps)$-approximation, matching the best known ratio for a single knapsack constraint.

We also study a variant of the {\em generalized assignment problem} (GAP) with group constraints. In this variant the items are partitioned into groups, and the solution gains profit from the assignment of an item (to one of the $m$ bins) only if all of the items in its group are assigned as well. We obtain a $\frac{1}{6}$-approximation algorithm for Group GAP instances where the total size of each group is at most $\frac{m}{2}$.

The other main direction of this research work is parameterized approximation algorithms. We introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms substantially improve the best known running times of parameterized approximation algorithms for Vertex Cover and $3$-Hitting Set for a wide range of approximation ratios.

The running times of our algorithms are derived from an asymptotic analysis of a broad class of two-variable recurrence relations. We derive a simple formula for this asymptotics. The formula can be efficiently calculated by solving a simple numerical optimization problem, and provides the mathematical insight required for the algorithm design. To this end, we show an equivalence between the recurrence and a stochastic process. We analyze this process using the Method of Types}, by introducing an adaptation of Sanov's theorem to our setting. We believe our novel analysis of recurrence relations which is of independent interest is a main contribution of this thesis.

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 2021
To the main CS technical reports page

Computer science department, Technion