Source author record

Pattara Sukprasert

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

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

In the $k$ -edge-connected spanning subgraph ( $k$ ECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to $k$ link failures: Given an $n$ -node $m$ -edge graph with a cost function on the edges, our goal is to compute a minimum-cost $k$ -edge-connected spanning subgraph. This NP-hard problem generalizes the minimum spanning tree problem and is the "uniform case" of a much broader class of survival network design problems (SNDP). A factor of two has remained the best approximation ratio for polynomial-time algorithms for the whole class of SNDP, even for a special case of $2$ ECSS. The fastest $2$ -approximation algorithm is however rather slow, taking $O(mn k)$ time [Khuller, Vishkin, STOC'92]. A faster time complexity of $O(n^2)$ can be obtained, but with a higher approximation guarantee of $(2k-1)$ [Gabow, Goemans, Williamson, IPCO'93]. Our main contribution is an algorithm that $(1+ε)$ -approximates the optimal fractional solution in $\tilde O(m/ε^2)$ time (independent of $k$ ), which can be turned into a $(2+ε)$ approximation algorithm that runs in time $\tilde O\left(\frac{m}{ε^2} + \frac{k^2n^{1.5}}{ε^2}\right)$ for (integral) $k$ ECSS; this improves the running time of the aforementioned results while keeping the approximation ratio arbitrarily close to a factor of two.

preprint2022arXiv

Individual Preference Stability for Clustering

In this paper, we propose a natural notion of individual preference (IP) stability for clustering, which asks that every data point, on average, is closer to the points in its own cluster than to the points in any other cluster. Our notion can be motivated from several perspectives, including game theory and algorithmic fairness. We study several questions related to our proposed notion. We first show that deciding whether a given data set allows for an IP-stable clustering in general is NP-hard. As a result, we explore the design of efficient algorithms for finding IP-stable clusterings in some restricted metric spaces. We present a polytime algorithm to find a clustering satisfying exact IP-stability on the real line, and an efficient algorithm to find an IP-stable 2-clustering for a tree metric. We also consider relaxing the stability constraint, i.e., every data point should not be too far from its own cluster compared to any other cluster. For this case, we provide polytime algorithms with different guarantees. We evaluate some of our algorithms and several standard clustering approaches on real data sets.

preprint2022arXiv

Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary

Designing dynamic algorithms against an adaptive adversary whose performance match the ones assuming an oblivious adversary is a major research program in the field of dynamic graph algorithms. One of the prominent examples whose oblivious-vs-adaptive gap remains maximally large is the \emph{fully dynamic spanner} problem; there exist algorithms assuming an oblivious adversary with near-optimal size-stretch trade-off using only $\operatorname{polylog}(n)$ update time [Baswana, Khurana, and Sarkar TALG'12; Forster and Goranci STOC'19; Bernstein, Forster, and Henzinger SODA'20], while against an adaptive adversary, even when we allow infinite time and only count recourse (i.e. the number of edge changes per update in the maintained spanner), all previous algorithms with stretch at most $\log^{5}(n)$ require at least $Ω(n)$ amortized recourse [Ausiello, Franciosa, and Italiano ESA'05]. In this paper, we completely close this gap with respect to recourse by showing algorithms against an adaptive adversary with near-optimal size-stretch trade-off and recourse. More precisely, for any $k\ge1$ , our algorithm maintains a $(2k-1)$ -spanner of size $O(n^{1+1/k}\log n)$ with $O(\log n)$ amortized recourse, which is optimal in all parameters up to a $O(\log n)$ factor. As a step toward algorithms with small update time (not just recourse), we show another algorithm that maintains a $3$ -spanner of size $\tilde O(n^{1.5})$ with $\operatorname{polylog}(n)$ amortized recourse \emph{and} simultaneously $\tilde O(\sqrt{n})$ worst-case update time.

preprint2021arXiv

Multi-transversals for Triangles and the Tuza's Conjecture

In this paper, we study a primal and dual relationship about triangles: For any graph $G$ , let $ν(G)$ be the maximum number of edge-disjoint triangles in $G$ , and $τ(G)$ be the minimum subset $F$ of edges such that $G \setminus F$ is triangle-free. It is easy to see that $ν(G) \leq τ(G) \leq 3 ν(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) \leq 2 ν(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 \geq 2$ , there exist a (multi)-set $F \subseteq E(G): |F| \leq 2k ν(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.

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.

Pattara Sukprasert

Research overview

Is this your work?

4 publications

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

Individual Preference Stability for Clustering

Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary

Multi-transversals for Triangles and the Tuza's Conjecture

See the researcher in context

Building this map preview