2 citations · 3 across the 6 of their papers we have counts for
9 papers
To Store or Not to Store: a graph theoretical approach for Dataset Versioning
Anxin Guo, Jingwei Li, Pattara Sukprasert +3
In this work, we study the cost efficient data versioning problem, where the goal is to optimize the storage and reconstruction (retrieval) costs of data versions, given a graph of…
Practical Parallel Algorithms for Near-Optimal Densest Subgraphs on Massive Graphs
Pattara Sukprasert, Quanquan C. Liu, Laxman Dhulipala +1
The densest subgraph problem has received significant attention, both in theory and in practice, due to its applications in problems such as community detection, social network ana…
Constant Approximation for Individual Preference Stable Clustering
Anders Aamand, Justin Y. Chen, Allen Liu +4
Individual preference (IP) stability, introduced by Ahmadi et al. (ICML 2022), is a natural clustering objective inspired by stability and fairness constraints. A clustering is …
Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary
Sayan Bhattacharya, Thatchaphol Saranurak, Pattara Sukprasert
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 grap…
Individual Preference Stability for Clustering
Saba Ahmadi, Pranjal Awasthi, Samir Khuller +4
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…
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai +3
In the -edge-connected spanning subgraph (ECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to link failures: Given an -nod…
Retraction: Improved Approximation Schemes for Dominating Set Problems in Unit Disk Graphs
Jittat Fakcharoenphol, Pattara Sukprasert
Retraction note: After posting the manuscript on arXiv, we were informed by Erik Jan van Leeuwen that both results were known and they appeared in his thesis[vL09]. A PTAS for MDS…
Multi-transversals for Triangles and the Tuza's Conjecture
Parinya Chalermsook, Samir Khuller, Pattara Sukprasert +1
In this paper, we study a primal and dual relationship about triangles: For any graph , let be the maximum number of edge-disjoint triangles in , and be the min…
Finding All Useless Arcs in Directed Planar Graphs
Jittat Fakcharoenphol, Bundit Laekhanukit, Pattara Sukprasert
We present a linear-time algorithm for simplifying flow networks on directed planar graphs: Given a directed planar graph on vertices, a source vertex and a sink vertex …