Qingyun Chen

NeurIPS Conference 2025 Conference Paper

A Beyond-Worst-Case Analysis of Greedy k-means++

• Qingyun Chen
• Sungjin Im
• Ben Moseley
• Ryan Milstrey
• Chenyang Xu
• Ruilong Zhang

$k$-means++ and the related greedy $k$-means++ algorithm are celebrated algorithms that efficiently compute seeds for Lloyd's algorithm. Greedy $k$-means++ is a generalization of $k$-means++ where, in each iteration, a new seed is greedily chosen among multiple $\ell \geq 2$ points sampled, as opposed to a single seed being sampled in $k$-means++. While empirical studies consistently show the superior performance of greedy $k$-means++, making it a preferred method in practice, a discrepancy exists between theory and practice. No theoretical justification currently explains this improved performance. Indeed, the prevailing theory suggests that greedy $k$-means++ exhibits worse performance than $k$-means++ in worst-case scenarios. This paper presents an analysis demonstrating the outperformance of the greedy algorithm compared to $k$-means++ for a natural class of well-separated instances with exponentially decaying distributions, such as Gaussian, specifically when $\ell = \Theta(\log k)$, a common parameter setting in practical applications.

SODA Conference 2025 Conference Paper

Online Scheduling via Gradient Descent for Weighted Flow Time Minimization

• Qingyun Chen
• Sungjin Im
• Aditya Petety

AAAI Conference 2024 Conference Paper

Sampling for Beyond-Worst-Case Online Ranking

• Qingyun Chen
• Sungjin Im
• Benjamin Moseley
• Chenyang Xu
• Ruilong Zhang

The feedback arc set problem is one of the most fundamental and well-studied ranking problems where n objects are to be ordered based on their pairwise comparison. The problem enjoys several efficient approximation algorithms in the offline setting. Unfortunately, online there are strong lower bounds on the competitive ratio establishing that no algorithm can perform well in the worst case. This paper introduces a new beyond-worst-case model for online feedback arc set. In the model, a sample of the input is given to the algorithm offline before the remaining instance is revealed online. This models the case in practice where yesterday's data is available and is similar to today's online instance. This sample is drawn from a known distribution which may not be uniform. We design an online algorithm with strong theoretical guarantees. The algorithm has a small constant competitive ratio when the sample is uniform---if not, we show we can recover the same result by adding a provably minimal sample. Empirical results validate the theory and show that such algorithms can be used on temporal data to obtain strong results.

AAAI Conference 2023 Conference Paper

Min-Max Submodular Ranking for Multiple Agents

• Qingyun Chen
• Sungjin Im
• Benjamin Moseley
• Chenyang Xu
• Ruilong Zhang

In the submodular ranking (SR) problem, the input consists of a set of submodular functions defined on a ground set of elements. The goal is to order elements for all the functions to have value above a certain threshold as soon on average as possible, assuming we choose one element per time. The problem is flexible enough to capture various applications in machine learning, including decision trees. This paper considers the min-max version of SR where multiple instances share the ground set. With the view of each instance being associated with an agent, the min-max problem is to order the common elements to minimize the maximum objective of all agents---thus, finding a fair solution for all agents. We give approximation algorithms for this problem and demonstrate their effectiveness in the application of finding a decision tree for multiple agents.

FOCS Conference 2022 Conference Paper

Survivable Network Design Revisited: Group-Connectivity

• Qingyun Chen
• Bundit Laekhanukit
• Chao Liao
• Yuhao Zhang 0001

In the classical survivable network design problem (SNDP), we are given an undirected graph $G-(V, E)$ with costs on edges and a connectivity requirement $k(5, t)$ for each pair of vertices. The goal is to find a minimum-cost subgraph $H\sqsubseteq G$ such that every pair $(s, t)$ are connected by $k(s, t)$ edge or (openly) vertex disjoint paths, abbreviated as EC-SNDP and VC-SNDP, respectively. The seminal result of Jain [FOCS’98, Combinatorica’01] gives a 2-approximation algorithm for EC-SNDP, and a decade later, an $O(k^{3}\log n)-$ approximation algorithm for VC-SNDP, where k is the largest connectivity requirement, was discovered by Chuzhoy and Khanna [FOCS’09, Theory Comput’12]. While there is a rich literature on point-to-point settings of SNDP, the viable case of connectivity between subsets is still relatively poorly understood. This paper concerns the generalization of SNDP into the subset-to-subset setting, namely Group EC-SNDR We develop the framework, which yields the first non-trivial (true) approximation algorithm for Group. EC-SNDE Previously only a bicriteria approximation algorithm is known for Group EC-SNDP [Chalermsook, Grandoni, and Laekhanukit, SODA’15l, and a true approximation algorithm is known only for the single-source variant with connectivity requirement $k(S, T)\in\{0, 1, 2\}$ [Gupta, Krishnaswamy, and Ravi, SODA’10; Khandekar, Kortsarz, and Nutov, FSTTCS’09 and Theor Comput. Sci’12].