Source author record

Jatin Batra

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

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover

We study the generalized min sum set cover (GMSSC) problem, wherein given a collection of hyperedges $E$ with arbitrary covering requirements $k_e$ , the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge $e$ is considered covered by the first time when $k_e$ many of its vertices appear in the ordering. We give a $4.642$ approximation algorithm for GMSSC, coming close to the best possible bound of $4$ , already for the classical special case (with all $k_e=1$ ) of min sum set cover (MSSC) studied by Feige, Lovász and Tetali, and improving upon the previous best known bound of $12.4$ due to Im, Sviridenko and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. This also gives an LP-based $4$ approximation for MSSC. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Another well-known special case is the min sum vertex cover (MSVC) problem, in which the input hypergraph is a graph and $k_e = 1$ , for every edge. We give a $16/9$ approximation for MSVC, and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best $1.999946$ approximation of Barenholz, Feige and Peleg. (The claimed $1.79$ approximation result of Iwata, Tetali and Tripathi for the MSVC turned out have an unfortunate, seemingly unfixable, mistake in it.) Finally, we revisit MSSC and consider the $\ell_p$ norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of $(p+1)^{1+1/p}$ , for all $p\ge 1$ . For $p=1$ , this gives yet another proof of the $4$ approximation for MSSC.

preprint2020arXiv

Non-uniform Geometric Set Cover and Scheduling on Multiple Machines

We consider the following general scheduling problem studied recently by Moseley. There are $n$ jobs, all released at time $0$ , where job $j$ has size $p_j$ and an associated arbitrary non-decreasing cost function $f_j$ of its completion time. The goal is to find a schedule on $m$ machines with minimum total cost. We give an $O(1)$ approximation for the problem, improving upon the previous $O(\log \log nP)$ bound ( $P$ is the maximum to minimum size ratio), and resolving the open question of Moseley. We first note that the scheduling problem can be reduced to a clean geometric set cover problem where points on a line with arbitrary demands, must be covered by a minimum cost collection of given intervals with non-uniform capacity profiles. Unfortunately, current techniques for such problems based on knapsack cover inequalities and low union complexity, completely lose the geometric structure in the non-uniform capacity profiles and incur at least an $Ω(\log\log P)$ loss. To this end, we consider general covering problems with non-uniform capacities, and give a new method to handle capacities in a way that completely preserves their geometric structure. This allows us to use sophisticated geometric ideas in a black-box way to avoid the $Ω(\log \log P)$ loss in previous approaches. In addition to the scheduling problem above, we use this approach to obtain $O(1)$ or inverse Ackermann type bounds for several basic capacitated covering problems.

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.