Zobrazeno 1 - 10
of 349
pro vyhledávání: '"Chekuri, Chandra"'
In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph $G=(V,E)$, a root vertex $r$ and a set $S \subseteq V$ of $k$ terminals. The goal is to find a min-cost subgraph that connects $r$ to each of the terminals. DST ad
Externí odkaz:
http://arxiv.org/abs/2407.01904
Autor:
Chekuri, Chandra, Song, Junkai
In the Priority $k$-Supplier problem the input consists of a metric space $(F \cup C, d)$ over set of facilities $F$ and a set of clients $C$, an integer $k > 0$, and a non-negative radius $r_v$ for each client $v \in C$. The goal is to select $k$ fa
Externí odkaz:
http://arxiv.org/abs/2406.14984
Autor:
Chekuri, Chandra, Jain, Rhea
We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results. We address multicommodity buy-at-bulk n
Externí odkaz:
http://arxiv.org/abs/2404.16725
Autor:
Chekuri, Chandra, Jain, Rhea
The Survivable Network Design problem (SNDP) is a well-studied problem, motivated by the design of networks that are robust to faults under the assumption that any subset of edges up to a specific number can fail. We consider non-uniform fault models
Externí odkaz:
http://arxiv.org/abs/2403.15547
We study fair distribution of a collection of m indivisible goods among a group of n agents, using the widely recognized fairness principles of Maximin Share (MMS) and Any Price Share (APS). These principles have undergone thorough investigation with
Externí odkaz:
http://arxiv.org/abs/2312.08504
Autor:
Chekuri, Chandra, Christiansen, Aleksander Bjørn, Holm, Jacob, van der Hoog, Ivor, Quanrud, Kent, Rotenberg, Eva, Schwiegelshohn, Chris
We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the edges such that the out-degree of each vertex is proportional to the ar
Externí odkaz:
http://arxiv.org/abs/2310.18146
Positive linear programs (LPs) model many graph and operations research problems. One can solve for a $(1+\epsilon)$-approximation for positive LPs, for any selected $\epsilon$, in polylogarithmic depth and near-linear work via variations of the mult
Externí odkaz:
http://arxiv.org/abs/2307.03307
Autor:
Chekuri, Chandra, Quanrud, Kent
Maximum weight independent set (MWIS) admits a $\frac1k$-approximation in inductively $k$-independent graphs and a $\frac{1}{2k}$-approximation in $k$-perfectly orientable graphs. These are a a parameterized class of graphs that generalize $k$-degene
Externí odkaz:
http://arxiv.org/abs/2307.02022
Autor:
Chekuri, Chandra, Torres, Manuel R.
Dense subgraph discovery is an important problem in graph mining and network analysis with several applications. Two canonical problems here are to find a maxcore (subgraph of maximum min degree) and to find a densest subgraph (subgraph of maximum av
Externí odkaz:
http://arxiv.org/abs/2306.02172
Boob et al. [1] described an iterative peeling algorithm called Greedy++ for the Densest Subgraph Problem (DSG) and conjectured that it converges to an optimum solution. Chekuri, Quanrud, and Torres [2] extended the algorithm to general supermodular
Externí odkaz:
http://arxiv.org/abs/2305.02987