Source author record

Prachi Goyal

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 math.CO

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

The Non-Uniform k-Center Problem

In this paper, we introduce and study the Non-Uniform k-Center problem (NUkC). Given a finite metric space $(X,d)$ and a collection of balls of radii $\{r_1\geq \cdots \ge r_k\}$ , the NUkC problem is to find a placement of their centers on the metric space and find the minimum dilation $α$ , such that the union of balls of radius $α\cdot r_i$ around the $i$ th center covers all the points in $X$ . This problem naturally arises as a min-max vehicle routing problem with fleets of different speeds. The NUkC problem generalizes the classic $k$ -center problem when all the $k$ radii are the same (which can be assumed to be $1$ after scaling). It also generalizes the $k$ -center with outliers (kCwO) problem when there are $k$ balls of radius $1$ and $\ell$ balls of radius $0$ . There are $2$ -approximation and $3$ -approximation algorithms known for these problems respectively; the former is best possible unless P=NP and the latter remains unimproved for 15 years. We first observe that no $O(1)$ -approximation is to the optimal dilation is possible unless P=NP, implying that the NUkC problem is more non-trivial than the above two problems. Our main algorithmic result is an $(O(1),O(1))$ -bi-criteria approximation result: we give an $O(1)$ -approximation to the optimal dilation, however, we may open $Θ(1)$ centers of each radii. Our techniques also allow us to prove a simple (uni-criteria), optimal $2$ -approximation to the kCwO problem improving upon the long-standing $3$ -factor. Our main technical contribution is a connection between the NUkC problem and the so-called firefighter problems on trees which have been studied recently in the TCS community.

preprint2014arXiv

Finding Even Subgraphs Even Faster

Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on $n$ vertices and a positive integer parameter $k$ , find if there exist $k$ edges (arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the vertices have even degrees---where the resulting graph is \emph{Eulerian}---the problem is called Undirected Eulerian Edge Deletion. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion. Cygan et al. [\emph{Algorithmica, 2014}] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time $2^{O(k \log k)}n^{O(1)}$ . They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$ . In this paper we answer their question in the affirmative: using the technique of computing \emph{representative families of co-graphic matroids} we design algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$ . The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. We believe that this view-point/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.

preprint2013arXiv

On the Parameterized Complexity of the Maximum Edge Coloring Problem

We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q>1 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q>1, and has been well-studied from the point of view of approximation. Our main focus is the case when q=2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.

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.