1 citations · 1 across the 16 of their papers we have counts for
18 papers · 1 filter
Tight Approximation Results for Matroid Optimization with a Linear Constraint
Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler
We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions , and a threshold…
A Tight Information-Theoretic Lower Bound for Randomized Online Set Cover
Ilan Doron-Arad, Joseph, Naor
Online set cover is a fundamental problem in online algorithms, admitting a deterministic -competitive algorithm, where is the number of sets and is the nu…
Incremental Dominating Set
Ilan Doron Arad, Jonathan Gal, Seffi Naor
Dominating Set is a fundamental problem in graph theory: given a graph, find a minimum-weight subset of vertices such that every vertex is either selected or adjacent to a selected…
You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
The -matroid intersection (-MI) problem asks if given matroids share a common basis. Already for , notable canonical NP-complete special cases are -…
Fine Grained Lower Bounds for Multidimensional Knapsack
Ilan Doron-Arad, Ariel Kulik, Pasin Manurangsi
We study the -dimensional knapsack problem. We are given a set of items, each with a -dimensional cost vector and a profit, along with a -dimensional budget vector. The go…
Unsplittable Flow on a Short Path
Ilan Doron-Arad, Fabrizio Grandoni, Ariel Kulik
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 su…
Non-Linear Paging
Ilan Doron-Arad, Joseph, Naor
We formulate and study non-linear paging - a broad model of online paging where the size of subsets of pages is determined by a monotone non-linear set function of the pages. This…
Approximations and Hardness of Packing Partially Ordered Items
Ilan Doron-Arad, Guy Kortsarz, Joseph Naor +2
Motivated by applications in production planning and storage allocation in hierarchical databases, we initiate the study of covering partially ordered items (CPO). Given a capacity…
An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
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…
Tight Bounds for Budgeted Maximum Weight Independent Set in Bipartite and Perfect Graphs
Ilan Doron-Arad, Hadas Shachnai
We consider the classic budgeted maximum weight independent set (BMWIS) problem. The input is a graph , a weight function , a cost f…
Budgeted Matroid Maximization: a Parameterized Viewpoint
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We study budgeted variants of well known maximization problems with multiple matroid constraints. Given an -matchoid $\cm$ on a ground set , a profit function $p:E \righta…
Lower Bounds for Matroid Optimization Problems with a Linear Constraint
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
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…
An FPTAS for Budgeted Laminar Matroid Independent Set
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
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…
Approximating Bin Packing with Conflict Graphs via Maximization Techniques
Ilan Doron-Arad, Hadas Shachnai
We give a comprehensive study of bin packing with conflicts (BPC). The input is a set of items, sizes , and a conflict graph . The goal is to…
An EPTAS for Budgeted Matching and Budgeted Matroid Intersection
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
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.…
Bin Packing with Partition Matroid can be Approximated within Bins
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We consider the Bin Packing problem with a partition matroid constraint. The input is a set of items of sizes in , and a partition matroid over the items. The goal is to pac…
An EPTAS for Budgeted Matroid Independent Set
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
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…
An APTAS for Bin Packing with Clique-graph Conflicts
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
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 nu…