6 citations · 20 across the 19 of their papers we have counts for
20 papers · 1 filter
Better Late Than Never: Online Flow Time Scheduling with Online Estimates
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
In the classical online flow-time scheduling problem on a single machine, jobs arrive over time and must be processed to minimize the total time they spend in the system: for over…
A Simpler Analysis for -Clairvoyant Flow Time Scheduling
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
We simplify the proof of the optimality of the Shortest Lower-Bound First (SLF) algorithm, introduced by Gupta, Kaplan, Lindermayr, Schlöter, and Yingchareonthawornchai [FOCS'25],…
A Little Clairvoyance Is All You Need
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
We revisit the classical problem of minimizing the total flow time of jobs on a single machine in the online setting where jobs arrive over time. It has long been known that the Sh…
Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
Olivier Fischer, Yonggang Jiang, Sagnik Mukhopadhyay +1
Vertex connectivity and its variants are among the most fundamental problems in graph theory, with decades of extensive study and numerous algorithmic advances. The directed varian…
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak +1
We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph vertices and edges in time. This breaks the long-sta…
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay +1
A recent breakthrough by [LNPSY STOC'21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequ…
Hardness Amplification for Dynamic Binary Search Trees
Shunhua Jiang, Victor Lecomte, Omri Weinstein +1
We prove direct-sum theorems for Wilber's two lower bounds [Wilber, FOCS'86] on the cost of access sequences in the binary search tree (BST) model. These bounds are central to the…
Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
Zhuan Khye Koh, Omri Weinstein, Sorrachai Yingchareonthawornchai
We present a nearly linear work parallel algorithm for approximating the Held-Karp bound for the Metric TSP problem. Given an edge-weighted undirected graph on edges…
The Group Access Bounds for Binary Search Trees
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak +2
The access lemma (Sleator and Tarjan, JACM 1985) is a property of binary search trees that implies interesting consequences such as static optimality, static finger, and working se…
Deterministic -Vertex Connectivity in Max-flows
Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
An -vertex -edge graph is \emph{-vertex connected} if it cannot be disconnected by deleting less than vertices. After more than half a century of intensive research, t…
Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
Parinya Chalermsook, Seth Pettie, Sorrachai Yingchareonthawornchai
We consider the problem of comparison-sorting an -permutation that avoids some -permutation . Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak prove that when …
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak +3
Greedy BST (or simply Greedy) is an online self-adjusting binary search tree defined in the geometric view ([Lucas, 1988; Munro, 2000; Demaine, Harmon, Iacono, Kane, Patrascu, SODA…
Deterministic Small Vertex Connectivity in Almost Linear Time
Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
In the vertex connectivity problem, given an undirected -vertex -edge graph , we need to compute the minimum number of vertices that can disconnect after removing them…
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…
Vertex Connectivity in Poly-logarithmic Max-flows
Jason Li, Danupon Nanongkai, Debmalya Panigrahi +2
The vertex connectivity of an -edge -vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In thi…
Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity
Max Franck, Sorrachai Yingchareonthawornchai
Vertex connectivity is a well-studied concept in graph theory with numerous applications. A graph is -connected if it remains connected after removing any vertices. The ve…
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak +2
Consider the following "local" cut-detection problem in a directed graph: We are given a seed vertex and need to remove at most edges so that at most edges can be reach…
Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex
Yu Gao, Jason Li, Danupon Nanongkai +3
We study deterministic algorithms for computing graph cuts, with focus on two fundamental problems: balanced sparse cut and -vertex connectivity for small ($k=O(\polylog n)$…
Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
We present a new, simple, algorithm for the local vertex connectivity problem (LocalVC) introduced by Nanongkai~et~al. [STOC'19]. Roughly, given an undirected unweighted graph ,…
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
Vertex connectivity a classic extensively-studied problem. Given an integer , its goal is to decide if an -node -edge graph can be disconnected by removing vertices. A…