Zobrazeno 1 - 10
of 1 153
pro vyhledávání: '"Chekuri A"'
Autor:
Chekuri, Chandra, Louis, Anand
We consider algorithms and spectral bounds for sparsest cut and conductance in directed polymatrodal networks. This is motivated by recent work on submodular hypergraphs \cite{Yoshida19,LiM18,ChenOT23,Veldt23} and previous work on multicommodity flow
Externí odkaz:
http://arxiv.org/abs/2410.20525
Autor:
Chekuri, Chandra, Jain, Rhea
We consider Directed Steiner Forest (DSF), a fundamental problem in network design. The input to DSF is a directed edge-weighted graph $G = (V, E)$ and a collection of vertex pairs $\{(s_i, t_i)\}_{i \in [k]}$. The goal is to find a minimum cost subg
Externí odkaz:
http://arxiv.org/abs/2410.17403
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:
Sen, Jaydip, Mayer, Joceli, Dasgupta, Subhasis, Nandi, Subrata, Krishnaswamy, Srinivasan, Mitra, Pinaki, Singh, Mahendra Pratap, Kundeti, Naga Prasanthi, MVP, Chandra Sekhara Rao, Chekuri, Sudha Sree, Pallapothu, Seshu Babu, Nanjundan, Preethi, George, Jossy P., Allahi, Abdelhadi El, Morino, Ilham, Oussous, Salma AIT, Beloualid, Siham, Tamtaoui, Ahmed, Bajit, Abderrahim
In the era of generative artificial intelligence and the Internet of Things, while there is explosive growth in the volume of data and the associated need for processing, analysis, and storage, several new challenges are faced in identifying spurious
Externí odkaz:
http://arxiv.org/abs/2404.00235
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