Search

The $\ell$-matroid intersection ($\ell$-MI) problem asks if $\ell$ given matroids share a common basis. Already for $\ell = 3$, notable canonical NP-complete special cases are $3$-Dimensional Matching and Hamiltonian Path on directed graphs. However, while these problems admit exponential-time algorithms that improve the simple brute force, the fastest known algorithm for $3$-MI is exactly brute force with runtime $2^{n}/poly(n)$, where $n$ is the number of elements. Our first result shows that in fact, brute force cannot be significantly improved, by ruling out an algorithm for $\ell$-MI with runtime $o\left(2^{n-5 \cdot n^{\frac{1}{\ell-1}} \cdot \log (n)}\right)$, for any fixed $\ell\geq 3$. The complexity gap between $3$-MI and the polynomially solvable $2$-matroid intersection calls for a better understanding of the complexity of intermediate problems. One such prominent problem is exact matroid intersection (EMI). Given two matroids whose elements are either red or blue and a number $k$, decide if there is a common basis which contains exactly $k$ red elements. We show that EMI does not admit a randomized polynomial time algorithm. This bound implies that the parameterized algorithm of Eisenbrand et al. (FOCS'24) for exact weight matroid cannot be generalized to matroid intersection. We further obtain: (i) an algorithm that solves $\ell$-MI faster than brute force in time $2^{n-\Omega\left(\log^2 (n)\right)} $ (ii) a parameterized running time lower bound of $2^{(\ell-2) \cdot k \cdot \log k} \cdot poly(n)$ for $\ell$-MI, where the parameter $k$ is the rank of the matroids. We obtain these two results by generalizing the Monotone Local Search technique of Fomin et al. (J. ACM'19). Broadly speaking, our generalization converts any parameterized algorithm for a subset problem into an exponential-time algorithm which is faster than brute-force.

In this paper we introduce Sampling with a Black Box, a generic technique for the design of parameterized approximation algorithms for vertex deletion problems (e.g., Vertex Cover, Feedback Vertex Set, etc.). The technique relies on two components: $\bullet$ A Sampling Step. A polynomial time randomized algorithm which given a graph $G$ returns a random vertex $v$ such that the optimum of $G\setminus \{v\}$ is smaller by $1$ than the optimum of $G$ with some prescribed probability $q$. We show such algorithms exists for multiple vertex deletion problems. $\bullet$ A Black Box algorithm which is either an exact parameterized algorithm or a polynomial time approximation algorithm. Our technique combines these two components together. The sampling step is applied iteratively to remove vertices from the input graph, and then the solution is extended using the black box algorithm. The process is repeated sufficiently many times so that the target approximation ratio is attained with a constant probability. The main novelty of our work lies in the analysis of the framework and the optimization of the parameters it uses. We use the technique to derive parameterized approximation algorithm for several vertex deletion problems, including Feedback Vertex Set, $d$-Hitting Set and $\ell$-Path Vertex Cover. In particular, for every approximation ratio $1<\beta<2$, we attain a parameterized $\beta$-approximation for Feedback Vertex Set which is faster than the parameterized $\beta$-approximation of [Jana, Lokshtanov, Mandal, Rai and Saurabh, MFCS 23']. Furthermore, our algorithms are always faster than the algorithms attained using Fidelity Preserving Transformations [Fellows, Kulik, Rosamond, and Shachnai, JCSS 18'].

We study the $d$-dimensional knapsack problem. We are given a set of items, each with a $d$-dimensional cost vector and a profit, along with a $d$-dimensional budget vector. The goal is to select a set of items that do not exceed the budget in all dimensions and maximize the total profit. A PTAS with running time $n^{\Theta(d/\varepsilon)}$ has long been known for this problem, where $\varepsilon$ is the error parameter and $n$ is the encoding size. Despite decades of active research, the best running time of a PTAS has remained $O(n^{\lceil d/\varepsilon \rceil - d})$. Unfortunately, existing lower bounds only cover the special case with two dimensions $d = 2$, and do not answer whether there is a $n^{o(d/\varepsilon)}$-time PTAS for larger values of $d$. The status of exact algorithms is similar: there is a simple $O(n \cdot W^d)$-time (exact) dynamic programming algorithm, where $W$ is the maximum budget, but there is no lower bound which explains the strong exponential dependence on $d$. In this work, we show that the running times of the best-known PTAS and exact algorithm cannot be improved up to a polylogarithmic factor assuming Gap-ETH. Our techniques are based on a robust reduction from 2-CSP, which embeds 2-CSP constraints into a desired number of dimensions, exhibiting tight trade-off between $d$ and $\varepsilon$ for most regimes of the parameters. Informally, we obtain the following main results for $d$-dimensional knapsack. No $n^{o(d/\varepsilon \cdot 1/(\log(d/\varepsilon))^2)}$-time $(1-\varepsilon)$-approximation for every $\varepsilon = O(1/\log d)$. No $(n+W)^{o(d/\log d)}$-time exact algorithm (assuming ETH). No $n^{o(\sqrt{d})}$-time $(1-\varepsilon)$-approximation for constant $\varepsilon$. $(d \cdot \log W)^{O(d^2)} + n^{O(1)}$-time $\Omega(1/\sqrt{d})$-approximation and a matching $n^{O(1)}$-time lower~bound.

In the Unsplittable Flow on a Path problem UFP, we are given a path graph with edge capacities and a collection of tasks. Each task is characterized by a demand, a profit, and a subpath. Our goal is to select a maximum profit subset of tasks such that the total demand of the selected tasks that use each edge $e$ is at most the capacity of $e$. Bag-UFP is the generalization of UFP where tasks are partitioned into bags, and we are allowed to select at most one task per bag. UFP admits a PTAS [Grandoni,M{\"o}mke,Wiese'22] but not an EPTAS [Wiese'17]. Bag-UFP is APX-hard [Spieksma'99] and the current best approximation is $O(\log n/\log\log n)$ [Grandoni,Ingala,Uniyal'15], where $n$ is the number of tasks. In this paper, we study the mentioned two problems when parameterized by the number $m$ of edges in the graph, with the goal of designing faster parameterized approximation algorithms. We present a parameterized EPTAS for Bag-UFP, and a substantially faster parameterized EPTAS for UFP (which is an FPTAS for $m=O(1)$). We also show that a parameterized FPTAS for UFP (hence for BagUFP) does not exist, therefore our results are qualitatively tight.

In a recent work, Esmer et al. describe a simple method - Approximate Monotone Local Search - to obtain exponential approximation algorithms from existing parameterized exact algorithms, polynomial-time approximation algorithms and, more generally, parameterized approximation algorithms. In this work, we generalize those results to the weighted setting. More formally, we consider monotone subset minimization problems over a weighted universe of size $n$ (e.g., Vertex Cover, $d$-Hitting Set and Feedback Vertex Set). We consider a model where the algorithm is only given access to a subroutine that finds a solution of weight at most $\alpha \cdot W$ (and of arbitrary cardinality) in time $c^k \cdot n^{O(1)}$ where $W$ is the minimum weight of a solution of cardinality at most $k$. In the unweighted setting, Esmer et al. determine the smallest value $d$ for which a $\beta$-approximation algorithm running in time $d^n \cdot n^{O(1)}$ can be obtained in this model. We show that the same dependencies also hold in a weighted setting in this model: for every fixed $\varepsilon>0$ we obtain a $\beta$-approximation algorithm running in time $O\left((d+\varepsilon)^{n}\right)$, for the same $d$ as in the unweighted setting. Similarly, we also extend a $\beta$-approximate brute-force search (in a model which only provides access to a membership oracle) to the weighted setting. Using existing approximation algorithms and exact parameterized algorithms for weighted problems, we obtain the first exponential-time $\beta$-approximation algorithms that are better than brute force for a variety of problems including Weighted Vertex Cover, Weighted $d$-Hitting Set, Weighted Feedback Vertex Set and Weighted Multicut.

In [Math. Oper. Res., 2011], Fleischer et al. introduced a powerful technique for solving the generic class of separable assignment problems (SAP), in which a set of items of given values and weights needs to be packed into a set of bins subject to separable assignment constraints, so as to maximize the total value. The approach of Fleischer at al. relies on solving a configuration LP and sampling a configuration for each bin independently based on the LP solution. While there is a SAP variant for which this approach yields the best possible approximation ratio, for various special cases, there are discrepancies between the approximation ratios obtained using the above approach and the state-of-the-art approximations. This raises the following natural question: Can we do better by iteratively solving the configuration LP and sampling a few bins at a time? To assess the potential gain from iterative randomized rounding, we consider as a case study one interesting SAP variant, namely, Uniform Cardinality Constrained Multiple Knapsack, for which we answer this question affirmatively. The input is a set of items, each has a value and a weight, and a set of uniform capacity bins. The goal is to assign a subset of the items of maximum total value to the bins such that $(i)$ the capacity of any bin is not exceeded, and $(ii)$ the number of items assigned to each bin satisfies a given cardinality constraint. While the technique of Fleischer et al. yields a $\left(1-\frac{1}{e}\right)$-approximation for the problem, we show that iterative randomized rounding leads to an efficient polynomial time approximation scheme (EPTAS), thus essentially resolving the complexity status of the problem. Our analysis of iterative randomized rounding can be useful for solving other SAP variants.

We study a family of matroid optimization problems with a linear constraint (MOL). In these problems, we seek a subset of elements which optimizes (i.e., maximizes or minimizes) a linear objective function subject to (i) a matroid independent set, or a matroid basis constraint, (ii) additional linear constraint. A notable member in this family is budgeted matroid independent set (BM), which can be viewed as classic $0/1$-knapsack with a matroid constraint. While special cases of BM, such as knapsack with cardinality constraint and multiple-choice knapsack, admit a fully polynomial-time approximation scheme (Fully PTAS), the best known result for BM on a general matroid is an Efficient PTAS. Prior to this work, the existence of a Fully PTAS for BM, and more generally, for any problem in the family of MOL problems, has been open. In this paper, we answer this question negatively by showing that none of the (non-trivial) problems in this family admits a Fully PTAS. This resolves the complexity status of several well studied problems. Our main result is obtained by showing first that exact weight matroid basis (EMB) does not admit a pseudo-polynomial time algorithm. This distinguishes EMB from the special cases of $k$-subset sum and EMB on a linear matroid, which are solvable in pseudo-polynomial time. We then obtain unconditional hardness results for the family of MOL problems in the oracle model (even if randomization is allowed), and show that the same results hold when the matroids are encoded as part of the input, assuming $P \neq NP$. For the hardness proof of EMB, we introduce the $\Pi$-matroid family. This intricate subclass of matroids, which exploits the interaction between a weight function and the matroid constraint, may find use in tackling other matroid optimization problems.

We study budgeted variants of well known maximization problems with multiple matroid constraints. Given an $\ell$-matchoid $\cm$ on a ground set $E$, a profit function $p:E \rightarrow \mathbb{R}_{\geq 0}$, a cost function $c:E \rightarrow \mathbb{R}_{\geq 0}$, and a budget $B \in \mathbb{R}_{\geq 0}$, the goal is to find in the $\ell$-matchoid a feasible set $S$ of maximum profit $p(S)$ subject to the budget constraint, i.e., $c(S) \leq B$. The {\em budgeted $\ell$-matchoid} (BM) problem includes as special cases budgeted $\ell$-dimensional matching and budgeted $\ell$-matroid intersection. A strong motivation for studying BM from parameterized viewpoint comes from the APX-hardness of unbudgeted $\ell$-dimensional matching (i.e., $B = \infty$) already for $\ell = 3$. Nevertheless, while there are known FPT algorithms for the unbudgeted variants of the above problems, the {\em budgeted} variants are studied here for the first time through the lens of parameterized complexity. We show that BM parametrized by solution size is $W[1]$-hard, already with a degenerate single matroid constraint. Thus, an exact parameterized algorithm is unlikely to exist, motivating the study of {\em FPT-approximation schemes} (FPAS). Our main result is an FPAS for BM (implying an FPAS for $\ell$-dimensional matching and budgeted $\ell$-matroid intersection), relying on the notion of representative set $-$ a small cardinality subset of elements which preserves the optimum up to a small factor. We also give a lower bound on the minimum possible size of a representative set which can be computed in polynomial time.

We study the uniform $2$-dimensional vector multiple knapsack (2VMK) problem, a natural variant of multiple knapsack arising in real-world applications such as virtual machine placement. The input for 2VMK is a set of items, each associated with a $2$-dimensional weight vector and a positive profit, along with $m$ $2$-dimensional bins of uniform (unit) capacity in each dimension. The goal is to find an assignment of a subset of the items to the bins, such that the total weight of items assigned to a single bin is at most one in each dimension, and the total profit is maximized. Our main result is a $(1- \frac{\ln 2}{2} - \varepsilon)$-approximation algorithm for 2VMK, for every fixed $\varepsilon > 0$, thus improving the best known ratio of $(1 - \frac{1}{e}-\varepsilon)$ which follows as a special case from a result of [Fleischer at al., MOR 2011]. Our algorithm relies on an adaptation of the Round$\&$Approx framework of [Bansal et al., SICOMP 2010], originally designed for set covering problems, to maximization problems. The algorithm uses randomized rounding of a configuration-LP solution to assign items to $\approx m\cdot \ln 2 \approx 0.693\cdot m$ of the bins, followed by a reduction to the ($1$-dimensional) Multiple Knapsack problem for assigning items to the remaining bins.

The goal of this paper is to understand how exponential-time approximation algorithms can be obtained from existing polynomial-time approximation algorithms, existing parameterized exact algorithms, and existing parameterized approximation algorithms. More formally, we consider a monotone subset minimization problem over a universe of size $n$ (e.g., Vertex Cover or Feedback Vertex Set). We have access to an algorithm that finds an $\alpha$-approximate solution in time $c^k \cdot n^{O(1)}$ if a solution of size $k$ exists (and more generally, an extension algorithm that can approximate in a similar way if a set can be extended to a solution with $k$ further elements). Our goal is to obtain a $d^n \cdot n^{O(1)}$ time $\beta$-approximation algorithm for the problem with $d$ as small as possible. That is, for every fixed $\alpha,c,\beta \geq 1$, we would like to determine the smallest possible $d$ that can be achieved in a model where our problem-specific knowledge is limited to checking the feasibility of a solution and invoking the $\alpha$-approximate extension algorithm. Our results completely resolve this question: (1) For every fixed $\alpha,c,\beta \geq 1$, a simple algorithm (``approximate monotone local search'') achieves the optimum value of $d$. (2) Given $\alpha,c,\beta \geq 1$, we can efficiently compute the optimum $d$ up to any precision $\varepsilon > 0$. Earlier work presented algorithms (but no lower bounds) for the special case $\alpha = \beta = 1$ [Fomin et al., J. ACM 2019] and for the special case $\alpha = \beta > 1$ [Esmer et al., ESA 2022]. Our work generalizes these results and in particular confirms that the earlier algorithms are optimal in these special cases., Comment: 80 pages, 5 figures

We study the budgeted laminar matroid independent set problem. The input is a ground set, where each element has a cost and a non-negative profit, along with a laminar matroid over the elements and a budget. The goal is to select a maximum profit independent set of the matroid whose total cost is bounded by the budget. Several well known special cases, where we have, e.g., no matroid constraint (the classic knapsack problem) or a uniform matroid constraint (knapsack with a cardinality constraint), admit a fully polynomial-time approximation scheme (FPTAS). In contrast, the budgeted matroid independent set (BMI) problem with a general matroid has an efficient polynomial-time approximation scheme (EPTAS) but does not admit an FPTAS. This implies an EPTAS for our problem, which is the best known result prior to this work. We present an FPTAS for budgeted laminar matroid independent set, improving the previous EPTAS for this matroid family and generalizing the FPTAS known for knapsack with a cardinality constraint and multiple-choice knapsack. Our scheme is based on a simple dynamic program which utilizes the tree-like structure of laminar matroids.

We study the budgeted versions of the well known matching and matroid intersection problems. While both problems admit a polynomial-time approximation scheme (PTAS) [Berger et al. (Math. Programming, 2011), Chekuri, Vondrak and Zenklusen (SODA 2011)], it has been an intriguing open question whether these problems admit a fully PTAS (FPTAS), or even an efficient PTAS (EPTAS). In this paper we answer the second part of this question affirmatively, by presenting an EPTAS for budgeted matching and budgeted matroid intersection. A main component of our scheme is a novel construction of representative sets for desired solutions, whose cardinality depends only on $\varepsilon$, the accuracy parameter. Thus, enumerating over solutions within a representative set leads to an EPTAS. This crucially distinguishes our algorithms from previous approaches, which rely on exhaustive enumeration over the solution set. Our ideas for constructing representative sets may find use in tackling other budgeted optimization problems, and are thus of independent interest.

We consider the Bin Packing problem with a partition matroid constraint. The input is a set of items of sizes in $(0,1]$, and a partition matroid over the items. The goal is to pack all items in a minimum number of unit-size bins, such that each bin forms an independent set in the matroid. The problem is a generalization of both Group Bin Packing and Bin Packing with Cardinality Constraints. Bin Packing with Partition Matroid naturally arises in resource allocation to ensure fault tolerance and security, as well as in harvesting computing capacity. Our main result is a polynomial-time algorithm that packs the items in $OPT + o(OPT)$ bins, where OPT is the minimum number of bins required for packing the given instance. This matches the best known result for the classic Bin Packing problem up to the function hidden by o(OPT). As special cases, our result improves upon the existing APTAS for Group Bin Packing and generalizes the AFTPAS for Bin Packing with Cardinality Constraints. Our approach is based on rounding a solution for a configuration-LP formulation of the problem. The rounding takes a novel point of view of prototypes in which items are interpreted as placeholders for other items and applies fractional grouping to modify a fractional solution (prototype) into one having nice integrality properties.

We consider the budgeted matroid independent set problem. The input is a ground set, where each element has a cost and a non-negative profit, along with a matroid over the elements and a budget. The goal is to select a subset of elements which maximizes the total profit subject to the matroid and budget constraints. Several well known special cases, where we have, e.g., a uniform matroid and a budget, or no matroid constraint (i.e., the classic knapsack problem), admit a fully polynomial-time approximation scheme (FPTAS). In contrast, already a slight generalization to the multi-budgeted matroid independent set problem has a PTAS but does not admit an efficient polynomial-time approximation scheme (EPTAS). This implies a PTAS for our problem, which is the best known result prior to this work. Our main contribution is an EPTAS for the budgeted matroid independent set problem. A key idea of the scheme is to find a representative set for the instance, whose cardinality depends solely on $1/\varepsilon$, where $\varepsilon > 0$ is the accuracy parameter of the scheme. The representative set is identified via matroid basis minimization, which can be solved by a simple greedy algorithm. Our scheme enumerates over subsets of the representative set and extends each subset using a linear program. The notion of representative sets may be useful in solving other variants of the budgeted matroid independent set problem.

In this paper, we consider a general notion of convolution. Let $D$ be a finite domain and let $D^n$ be the set of $n$-length vectors (tuples) of $D$. Let $f : D \times D \to D$ be a function and let $\oplus_f$ be a coordinate-wise application of $f$. The $f$-Convolution of two functions $g,h : D^n \to \{-M,\ldots,M\}$ is $$(g \otimes_f h)(\textbf{v}) := \sum_{\substack{\textbf{v}_g,\textbf{v}_h \in D^n\\ \text{s.t. } \textbf{v}_g \oplus_f \textbf{v}_h}} g(\textbf{v}_g) \cdot h(\textbf{v}_h)$$ for every $\textbf{v} \in D^n$. This problem generalizes many fundamental convolutions such as Subset Convolution, XOR Product, Covering Product or Packing Product, etc. For arbitrary function $f$ and domain $D$ we can compute $f$-Convolution via brute-force enumeration in $\widetilde{O}(|D|^{2n}\mathrm{polylog}(M))$ time. Our main result is an improvement over this naive algorithm. We show that $f$-Convolution can be computed exactly in $\widetilde{O}((c \cdot |D|^2)^{n}\mathrm{polylog}(M))$ for constant $c := 3/4$ when $D$ has even cardinality. Our main observation is that a \emph{cyclic partition} of a function $f : D \times D \to D$ can be used to speed up the computation of $f$-Convolution, and we show that an appropriate cyclic partition exists for every $f$. Furthermore, we demonstrate that a single entry of the $f$-Convolution can be computed more efficiently. In this variant, we are given two functions $g,h : D^n \to \{-M,\ldots,M\}$ alongside with a vector $\textbf{v} \in D^n$ and the task of the $f$-Query problem is to compute integer $(g \otimes_f h)(\textbf{v})$. This is a generalization of the well-known Orthogonal Vectors problem. We show that $f$-Query can be computed in $\widetilde{O}(|D|^{\frac{\omega}{2} n}\mathrm{polylog}(M))$ time, where $\omega \in [2,2.372)$ is the exponent of currently fastest matrix multiplication algorithm., Comment: We improved constant c, 29 pages, 5 colored figures

We generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J.ACM 2019], by establishing a connection between parameterized approximation and exponential-time approximation algorithms for monotone subset minimization problems. In a monotone subset minimization problem the input implicitly describes a non-empty set family over a universe of size $n$ which is closed under taking supersets. The task is to find a minimum cardinality set in this family. Broadly speaking, we use approximate monotone local search to show that a parameterized $\alpha$-approximation algorithm that runs in $c^k \cdot n^{O(1)}$ time, where $k$ is the solution size, can be used to derive an $\alpha$-approximation randomized algorithm that runs in $d^n \cdot n^{O(1)}$ time, where $d$ is the unique value in $d \in (1,1+\frac{c-1}{\alpha})$ such that $\mathcal{D}(\frac{1}{\alpha}\|\frac{d-1}{c-1})=\frac{\ln c}{\alpha}$ and $\mathcal{D}(a \|b)$ is the Kullback-Leibler divergence. This running time matches that of Fomin et al. for $\alpha=1$, and is strictly better when $\alpha >1$, for any $c > 1$. Furthermore, we also show that this result can be derandomized at the expense of a sub-exponential multiplicative factor in the running time. We demonstrate the potential of approximate monotone local search by deriving new and faster exponential approximation algorithms for Vertex Cover, $3$-Hitting Set, Directed Feedback Vertex Set, Directed Subset Feedback Vertex Set, Directed Odd Cycle Transversal and Undirected Multicut. For instance, we get a $1.1$-approximation algorithm for Vertex Cover with running time $1.114^n \cdot n^{O(1)}$, improving upon the previously best known $1.1$-approximation running in time $1.127^n \cdot n^{O(1)}$ by Bourgeois et al. [DAM 2011]., Comment: 27 pages, full version of a paper accepted at ESA 2022

We study the $d$-dimensional Vector Bin Packing ($d$VBP) problem, a generalization of Bin Packing with central applications in resource allocation and scheduling. In $d$VBP, we are given a set of items, each of which is characterized by a $d$-dimensional volume vector; the objective is to partition the items into a minimum number of subsets (bins), such that the total volume of items in each subset is at most $1$ in each dimension. Our main result is an asymptotic approximation algorithm for $d$VBP that yields a ratio of $(1+\ln d-\chi(d) +\varepsilon)$ for all $d \in \mathbb{N}$ and any $\varepsilon > 0$; here, $\chi(d)$ is some strictly positive function. This improves upon the best known asymptotic ratio of $ \left(1+ \ln d +\varepsilon\right)$ due to Bansal, Caprara and Sviridenko (SICOMP 2010) for any $d >3$. By slightly modifying our algorithm to include an initial matching phase and applying a tighter analysis we obtain an asymptotic approximation ratio of $\left(\frac{4}{3}+\varepsilon\right)$ for the special case of $d=2$, thus substantially improving the previous best ratio of $\left(\frac{3}{2}+\varepsilon\right)$ due to Bansal, Elias and Khan (SODA 2016). Our algorithm iteratively solves a configuration LP relaxation for the residual instance (from previous iterations) and samples a small number of configurations based on the solution for the configuration LP. While iterative rounding was already used by Karmarkar and Karp (FOCS 1982) to establish their celebrated result for classic (one-dimensional) Bin Packing, iterative randomized rounding is used here for the first time in the context of (Vector) Bin Packing. Our results show that iterative randomized rounding is a powerful tool for approximating $d$VBP, leading to simple algorithms with improved approximation guarantees.

The world is dynamic and changes over time, thus any optimization problem used to model real life problems must address this dynamic nature, taking into account the cost of changes to a solution over time. The multistage model was introduced with this goal in mind. In this model we are given a series of instances of an optimization problem, corresponding to different times, and a solution is provided for each instance. The strive for obtaining near-optimal solutions for each instance on one hand, while maintaining similar solutions for consecutive time units on the other hand, is quantified and integrated into the objective function. In this paper we consider the Generalized Multistage $d$-Knapsack problem, a generalization of the multistage variants of the Multiple Knapsack problem, as well as the $d$-Dimensional Knapsack problem. We present a PTAS for Generalized Multistage $d$-Knapsack.

Many algorithms for maximizing a monotone submodular function subject to a knapsack constraint rely on the natural greedy heuristic. We present a novel refined analysis of this greedy 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.

We study the following variant of the classic {\em bin packing} problem. Given a set of items of various sizes, partitioned into groups, find a packing of the items in a minimum number of identical (unit-size) bins, such that no two items of the same group are assigned to the same bin. This problem, known as {\em bin packing with clique-graph conflicts}, has natural applications in storing file replicas, security in cloud computing and signal distribution. Our main result is an {\em asymptotic polynomial time approximation scheme (APTAS)} for the problem, improving upon the best known ratio of $2$. %In particular, for any instance $I$ and a fixed $\eps \in (0,1)$, the items are packed in at most $(1+\eps)OPT(I) +1$ bins, where $OPT(I)$ is the minimum number of bins required for packing the instance. As a key tool, we apply a novel {\em Shift \& Swap} technique which generalizes the classic linear shifting technique to scenarios allowing conflicts between items. The major challenge of packing {\em small} items using only a small number of extra bins is tackled through an intricate combination of enumeration and a greedy-based approach that utilizes the rounded solution of a {\em linear program}.

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 paper 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 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-\varepsilon)$-approximation, matching the best known ratio for a single knapsack constraint. The robustness of our algorithm is achieved by applying a novel fractional variant of the classical linear grouping technique, which is of independent interest.

We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint. The input is a set $I$ of items, each has a non-negative weight, and a set of bins of arbitrary capacities. Also, we are given a submodular, monotone and non-negative function $f$ over subsets of the items. The objective is to find a packing of a subset of items $A \subseteq I$ in the bins such that $f(A)$ is maximized. Our main result is an almost optimal polynomial time $(1-e^{-1}-\varepsilon)$-approximation algorithm for the problem, for any $\varepsilon>0$. The algorithm relies on a structuring technique which converts a general multiple knapsack constraint to a constraint in which the bins are partitioned into groups of exponentially increasing cardinalities, each consisting of bins of uniform capacity. We derive the result by combining structuring with a refined analysis of techniques for submodular optimization subject to knapsack constraints.

In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms improve the best known running times of parameterized approximation algorithms for Vertex Cover and $3$-Hitting Set for a wide range of approximation ratios. One notable example is a simple parameterized random $1.5$-approximation algorithm for Vertex Cover, whose running time of $O^*(1.01657^k)$ substantially improves the best known runnning time of $O^*(1.0883^k)$ [Brankovic and Fernau, 2013]. For $3$-Hitting Set we present a parameterized random $2$-approximation algorithm with running time of $O^*(1.0659^k)$, improving the best known $O^*(1.29^k)$ algorithm of [Brankovic and Fernau, 2012]. The running times of our algorithms are derived from an asymptotic analysis of a wide class of two-variable recurrence relations of the form: $$p(b,k) = \min_{1\leq j \leq N} \sum_{i=1}^{r_j} \bar{\gamma}_i^j \cdot p(b-\bar{b}^j_i, k-\bar{k}_i^j),$$ where $\bar{b}^j$ and $\bar{k}^j$ are vectors of natural numbers, and $\bar{\gamma}^j$ is a probability distribution over $r_j$ elements, for $1\leq j \leq N$. Our main theorem asserts that for any $\alpha>0$, $$\lim_{k \rightarrow \infty } \frac{1}{k} \log p(\alpha k,k) = -\max_{1\leq j \leq N} M_j,$$ where $M_j$ depends only on $\alpha$, $\bar{\gamma}^j$, $\bar{b}^j$ and $\bar{k}^j$, and can be efficiently calculated by solving a simple numerical optimization problem. 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 paper.

We study a variant of the \emph{generalized assignment problem} ({\sf GAP}) with group constraints. An instance of {\sf Group GAP} is a set $I$ of items, partitioned into $L$ groups, and a set of $m$ uniform (unit-sized) bins. Each item $i \in I$ has a size $s_i >0$, and a profit $p_{i,j} \geq 0$ if packed in bin $j$. A group of items is \emph{satisfied} if all of its items are packed. The goal is to find a feasible packing of a subset of the items in the bins such that the total profit from satisfied groups is maximized. We point to central applications of {\sf Group GAP} in Video-on-Demand services, mobile Device-to-Device network caching and base station cooperation in 5G networks. Our main result is a $\frac{1}{6}$-approximation algorithm for {\sf Group GAP} instances where the total size of each group is at most $\frac{m}{2}$. At the heart of our algorithm lies an interesting derivation of a submodular function from the classic LP formulation of {\sf GAP}, which facilitates the construction of a high profit solution utilizing at most half the total bin capacity, while the other half is \emph{reserved} for later use. In particular, we give an algorithm for submodular maximization subject to a knapsack constraint, which finds a solution of profit at least $\frac{1}{3}$ of the optimum, using at most half the knapsack capacity, under mild restrictions on element sizes. Our novel approach of submodular optimization subject to a knapsack \emph{with reserved capacity} constraint may find applications in solving other group assignment problems., Comment: Preliminary version to appear in European Symposium on Algorithms 2019

We prove a general result demonstrating the power of Lagrangian relaxation in solving constrained maximization problems with arbitrary objective functions. This yields a unified approach for solving a wide class of {\em subset selection} problems with linear constraints. Given a problem in this class and some small $\eps \in (0,1)$, we show that if there exists an $r$-approximation algorithm for the Lagrangian relaxation of the problem, for some $r \in (0,1)$, then our technique achieves a ratio of $\frac{r}{r+1} -\! \eps$ to the optimal, and this ratio is tight. The number of calls to the $r$-approximation algorithm, used by our algorithms, is {\em linear} in the input size and in $\log (1 / \eps)$ for inputs with cardinality constraint, and polynomial in the input size and in $\log (1 / \eps)$ for inputs with arbitrary linear constraint. Using the technique we obtain (re)approximation algorithms for natural (reoptimization) variants of classic subset selection problems, including real-time scheduling, the {\em maximum generalized assignment problem (GAP)} and maximum weight independent set.

Submodular maximization generalizes many fundamental problems in discrete optimization, including Max-Cut in directed/undirected graphs, maximum coverage, maximum facility location and marketing over social networks. In this paper we consider the problem of maximizing any submodular function subject to $d$ knapsack constraints, where $d$ is a fixed constant. We establish a strong relation between the discrete problem and its continuous relaxation, obtained through {\em extension by expectation} of the submodular function. Formally, we show that, for any non-negative submodular function, an $\alpha$-approximation algorithm for the continuous relaxation implies a randomized $(\alpha - \eps)$-approximation algorithm for the discrete problem. We use this relation to improve the best known approximation ratio for the problem to $1/4- \eps$, for any $\eps > 0$, and to obtain a nearly optimal $(1-e^{-1}-\eps)-$approximation ratio for the monotone case, for any $\eps>0$. We further show that the probabilistic domain defined by a continuous solution can be reduced to yield a polynomial size domain, given an oracle for the extension by expectation. This leads to a deterministic version of our technique., Comment: A preliminary version of this paper appeared in the Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, New York, January 2009