Sumedha Uniyal

Sumedha Uniyal

Auto-generated profile, based on publicly available information

Sumedha Uniyal

University of Lugano

Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications

1 January 2015
Verified
Book Chapter
Closed access
PDF file
FGFabrizio Grandoni
Fabrizio Grandoni
SISalvatore Ingala
Salvatore Ingala
SUSumedha Uniyal
Sumedha Uniyal

1 January 2020
Verified
Book Chapter
Closed access
PCParinya Chalermsook
Parinya Chalermsook
SKSamir Khuller
Samir Khuller
PSPattara Sukprasert
Pattara Sukprasert
SUSumedha Uniyal
Sumedha Uniyal
In this paper, we study a primal and dual relationship about triangles: For any graph G, let v(G) be the maximum number of edge-disjoint triangles in G, and τ(G) be the minimum subset F of edges such that G \ F is triangle-free. It is easy to see that v(G) ≤ τ(G) ≤ 3v(G), and in fact, this rather obvious inequality holds for a much more general primal-dual relation between k-hyper matching and covering in hypergraphs. Tuza conjectured in 1981 that τ(G) ≤ 2v(G), and this question has received attention from various groups of researchers in discrete mathematics, settling various special cases such as planar graphs and generalized to bounded maximum average degree graphs, some cases of minor-free graphs, and very dense graphs. Despite these efforts, the conjecture in general graphs has remained wide open for almost four decades. In this paper, we provide a proof of a non-trivial consequence of the conjecture; that is, for every k ≥ 2, there exist a (multi)-set F ⊆ E(G): |F| ≤ 2kv(G) such that each triangle in G overlaps at least k elements in F. Our result can be seen as a strengthened statement of Krivelevich's result on the fractional version of Tuza's conjecture (and we give some examples illustrating this.) The main technical ingredient of our result is a charging argument, that locally identifies edges in F based on a local view of the packing solution. This idea might be useful in further studying the primal-dual relations in general and the Tuza's conjecture in particular.

3 December 2020
Verified
Book Chapter
Closed access
PDF file
JBJarosław Byrka
Jarosław Byrka
MLMateusz Lewandowski
Mateusz Lewandowski
SMSyed Mohammad Meesum
Syed Mohammad Meesum
JSJoachim Spoerhase
Joachim Spoerhase
SUSumedha Uniyal
Sumedha Uniyal

23 November 2015 in arXiv
Verified
Preprint
Open access
PDF file
JBJarosław Byrka
Jarosław Byrka
BRBartosz Rybicki
Bartosz Rybicki
SUSumedha Uniyal
Sumedha Uniyal
We study the Capacitated k-Median problem, for which all the known constant factor approximation algorithms violate either the number of facilities or the capacities. While the standard LP-relaxation can only be used for algorithms violating one of the two by a factor of at least two, Shi Li [SODA'15, SODA'16] gave algorithms violating the number of facilities by a factor of 1+{\epsilon} exploring properties of extended relaxations. In this paper we develop a constant factor approximation algorithm for Uniform Capacitated k-Median violating only the capacities by a factor of 1+{\epsilon}. The algorithm is based on a configuration LP. Unlike in the algorithms violating the number of facilities, we cannot simply open extra few facilities at selected locations. Instead, our algorithm decides about the facility openings in a carefully designed dependent rounding process.

22 January 2024 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
PCParinya Chalermsook
Parinya Chalermsook
MKMatthias Kaul
Matthias Kaul
MMMatthias Mnich
Matthias Mnich
JSJoachim Spoerhase
Joachim Spoerhase
SUSumedha Uniyal
Sumedha Uniyal
DVDaniel Vaz
Daniel Vaz
The fundamental Sparsest Cut problem takes as input a graph G together with edge capacities and demands and seeks a cut that minimizes the ratio between the capacities and demands across the cuts. For n -vertex graphs G of treewidth k , Chlamtáč, Krauthgamer, and Raghavendra (APPROX’10) presented an algorithm that yields a factor- \(2^{2^k}\) approximation in time \(2^{O(k)} \cdot n^{O(1)}\) . Later, Gupta, Talwar, and Witmer (STOC’13) showed how to obtain a 2-approximation algorithm with a blown-up runtime of \(n^{O(k)}\) . An intriguing open question is whether one can simultaneously achieve the best out of the aforementioned results, that is, a factor-2 approximation in time \(2^{O(k)} \cdot n^{O(1)}\) . In this article, we make significant progress towards this goal via the following results: (i) A factor- \(O(k^2)\) approximation that runs in time \(2^{O(k)} \cdot n^{O(1)}\) , directly improving the work of Chlamtáč et al. while keeping the runtime single-exponential in k . (ii) For any \(\varepsilon \in (0,1]\) , a factor- \(O(1/\varepsilon ^2)\) approximation whose runtime is \(2^{O(k^{1+\varepsilon }/\varepsilon)} \cdot n^{O(1)}\) , implying a constant-factor approximation whose runtime is nearly single-exponential in k and a factor- \(O(\log ^2 k)\) approximation in time \(k^{O(k)} \cdot n^{O(1)}\) . Key to these results is a new measure of a tree decomposition that we call combinatorial diameter , which may be of independent interest.