Source author record

Hadas Shachnai

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

8works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

An EPTAS for Budgeted Matroid Independent Set

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.

preprint2016arXiv

Flexible Resource Allocation for Clouds and All-Optical Networks

Motivated by the cloud computing paradigm, and by key optimization problems in all-optical networks, we study two variants of the classic job interval scheduling problem, where a reusable resource is allocated to competing job intervals in a flexible manner. Each job, $J_i$ , requires the use of up to $r_{max}(i)$ units of the resource, with a profit of $p_i \geq 1$ accrued for each allocated unit. The goal is to feasibly schedule a subset of the jobs so as to maximize the total profit. The resource can be allocated either in contiguous or non-contiguous blocks. These problems can be viewed as flexible variants of the well known storage allocation and bandwidth allocation problems. We show that the contiguous version is strongly NP-hard, already for instances where all jobs have the same profit and the same maximum resource requirement. For such instances, we derive the best possible positive result, namely, a polynomial time approximation scheme. We further show that the contiguous variant admits a $(\frac{5}{4} + \varepsilon)$ -approximation algorithm, for any fixed $\varepsilon > 0$ , on instances whose job intervals form a proper interval graph. At the heart of the algorithm lies a non-standard parameterization of the approximation ratio itself, which is of independent interest. For the non-contiguous case, we uncover an interesting relation to the paging problem that leads to a simple $O(n \log n)$ algorithm for uniform profit instances of n jobs. The algorithm is easy to implement and is thus practical.

preprint2015arXiv

A Multivariate Framework for Weighted FPT Algorithms

We introduce a novel multivariate approach for solving weighted parameterized problems. In our model, given an instance of size $n$ of a minimization (maximization) problem, and a parameter $W \geq 1$ , we seek a solution of weight at most (or at least) $W$ . We use our general framework to obtain efficient algorithms for such fundamental graph problems as Vertex Cover, 3-Hitting Set, Edge Dominating Set and Max Internal Out-Branching. The best known algorithms for these problems admit running times of the form $c^W n^{O(1)}$ , for some constant $c>1$ . We improve these running times to $c^s n^{O(1)}$ , where $s\leq W$ is the minimum size of a solution of weight at most (at least) $W$ . If no such solution exists, $s=\min\{W,m\}$ , where $m$ is the maximum size of a solution. Clearly, $s$ can be substantially smaller than $W$ . In particular, the running times of our algorithms are (almost) the same as the best known $O^*$ running times for the unweighted variants. Thus, we solve the weighted versions of * Vertex Cover in $1.381^s n^{O(1)}$ time and $n^{O(1)}$ space. * 3-Hitting Set in $2.168^s n^{O(1)}$ time and $n^{O(1)}$ space. * Edge Dominating Set in $2.315^s n^{O(1)}$ time and $n^{O(1)}$ space. * Max Internal Out-Branching in $6.855^s n^{O(1)}$ time and space. We further show that Weighted Vertex Cover and Weighted Edge Dominating Set admit fast algorithms whose running times are of the form $c^t n^{O(1)}$ , where $t \leq s$ is the minimum size of a solution.

preprint2015arXiv

On Lagrangian Relaxation and Reoptimization Problems

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.

preprint2014arXiv

Parameterized Algorithms for Graph Partitioning Problems

We study a broad class of graph partitioning problems, where each problem is specified by a graph $G=(V,E)$ , and parameters $k$ and $p$ . We seek a subset $U\subseteq V$ of size $k$ , such that $α_1m_1 + α_2m_2$ is at most (or at least) $p$ , where $α_1,α_2\in\mathbb{R}$ are constants defining the problem, and $m_1, m_2$ are the cardinalities of the edge sets having both endpoints, and exactly one endpoint, in $U$ , respectively. This class of fixed cardinality graph partitioning problems (FGPP) encompasses Max $(k,n-k)$ -Cut, Min $k$ -Vertex Cover, $k$ -Densest Subgraph, and $k$ -Sparsest Subgraph. Our main result is an $O^*(4^{k+o(k)}Δ^k)$ algorithm for any problem in this class, where $Δ\geq 1$ is the maximum degree in the input graph. This resolves an open question posed by Bonnet et al. [IPEC 2013]. We obtain faster algorithms for certain subclasses of FGPPs, parameterized by $p$ , or by $(k+p)$ . In particular, we give an $O^*(4^{p+o(p)})$ time algorithm for Max $(k,n-k)$ -Cut, thus improving significantly the best known $O^*(p^p)$ time algorithm.

preprint2014arXiv

Representative Families: A Unified Tradeoff-Based Approach

Let $M=(E,{\cal I})$ be a matroid, and let $\cal S$ be a family of subsets of size $p$ of $E$ . A subfamily $\widehat{\cal S}\subseteq{\cal S}$ represents ${\cal S}$ if for every pair of sets $X\in{\cal S}$ and $Y\subseteq E\setminus X$ such that $X\cup Y\in{\cal I}$ , there is a set $\widehat{X}\in\widehat{\cal S}$ disjoint from $Y$ such that $\widehat{X}\cup Y\in{\cal I}$ . Fomin et al. (Proc. ACM-SIAM Symposium on Discrete Algorithms, 2014) introduced a powerful technique for fast computation of representative families for uniform matroids. In this paper, we show that this technique leads to a unified approach for substantially improving the running times of parameterized algorithms for some classic problems. This includes, among others, $k$ -Partial Cover, $k$ -Internal Out-Branching, and Long Directed Cycle. Our approach exploits an interesting tradeoff between running time and the size of the representative families.

preprint2014arXiv

Tighter Bounds for Makespan Minimization on Unrelated Machines

We consider the problem of scheduling $n$ jobs to minimize the makespan on $m$ unrelated machines, where job $j$ requires time $p_{ij}$ if processed on machine $i$ . A classic algorithm of Lenstra et al. yields the best known approximation ratio of $2$ for the problem. Improving this bound has been a prominent open problem for over two decades. In this paper we obtain a tighter bound for a wide subclass of instances which can be identified efficiently. Specifically, we define the feasibility factor of a given instance as the minimum fraction of machines on which each job can be processed. We show that there is a polynomial-time algorithm that, given values $L$ and $T$ , and an instance having a sufficiently large feasibility factor $h \in (0,1]$ , either proves that no schedule of mean machine completion time $L$ and makespan $T$ exists, or else finds a schedule of makespan at most $T + L/h < 2T$ . For the restricted version of the problem, where for each job $j$ and machine $i$ , $p_{ij} \in \{p_j, \infty\}$ , we show that a simpler algorithm yields a better bound, thus improving for highly feasible instances the best known ratio of $33/17 + ε$ , for any fixed $ε>0$ , due to Svensson.

preprint2011arXiv

Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints

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 $α$ -approximation algorithm for the continuous relaxation implies a randomized $(α- \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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Hadas Shachnai

Research overview

Is this your work?

8 publications

An EPTAS for Budgeted Matroid Independent Set

Flexible Resource Allocation for Clouds and All-Optical Networks

A Multivariate Framework for Weighted FPT Algorithms

On Lagrangian Relaxation and Reoptimization Problems

Parameterized Algorithms for Graph Partitioning Problems

Representative Families: A Unified Tradeoff-Based Approach

Tighter Bounds for Makespan Minimization on Unrelated Machines

Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints

See the researcher in context

Building this map preview