192 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Fudan UniversityCN23 papers
- Shanghai Jiao Tong UniversityCN16 papers
- Peking UniversityCN14 papers
- Chinese University of Hong KongHK11 papers
- Tsinghua UniversityCN10 papers
- University of MinnesotaUS9 papers
- Nanyang Technological UniversitySG8 papers
- Hong Kong University of Science and TechnologyHK7 papers
- University of Hong KongHK7 papers
- University of WashingtonUS7 papers
- Stanford UniversityUS6 papers
- University of Minnesota SystemUS6 papers
12 papers · 1 filter
On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
Tsz Chiu Kwok, Zhewei Wei, Mingji Yang
We initiate a study of solving a row/column diagonally dominant (RDD/CDD) linear system in sublinear time, with the goal of estimating for a given vector $t\in…
(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics
Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu
Motivated by display advertising on the internet, the online stochastic matching problem is proposed by Feldman, Mehta, Mirrokni, and Muthukrishnan (FOCS 2009). Consider a stochast…
Generalized Sorting with Predictions
Pinyan Lu, Xuandi Ren, Enze Sun +1
Generalized sorting problem, also known as sorting with forbidden comparisons, was first introduced by Huang et al. together with a randomized algorithm which requires $\tilde O(n^…
On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit +1
We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour t…
Fully Online Matching II: Beating Ranking and Water-filling
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu +1
Karp, Vazirani, and Vazirani (STOC 1990) initiated the study of online bipartite matching, which has held a central role in online algorithms ever since. Of particular importance a…
Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler
Zhengfeng Ji, Zhihan Jin, Pinyan Lu
The algorithm and complexity of approximating the permanent of a matrix is an extensively studied topic. Recently, its connection with quantum supremacy and more specifically Boson…
Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio
Minming Li, Pinyan Lu, Yuhao Yao +1
In this paper, we study the two-facility location game on a line with optional preference where the acceptable set of facilities for each agent could be different and an agent's co…
-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
Fabrizio Grandoni, Bundit Laekhanukit, Shi Li
In the Directed Steiner Tree (DST) problem we are given an -vertex directed edge-weighted graph, a root , and a collection of terminal nodes. Our goal is to find a minimu…
On subexponential running times for approximating directed Steiner tree and related problems
Marek Cygan, Guy Kortsarz, Bundit Laekhanukit
This paper concerns proving almost tight (super-polynomial) running times, for achieving desired approximation ratios for various problems. To illustrate, the question we study, le…
Nearly Tight Bounds for Sandpile Transience on the Grid
David Durfee, Matthew Fahrbach, Yu Gao +1
We use techniques from the theory of electrical networks to give nearly tight bounds for the transience class of the Abelian sandpile model on the two-dimensional grid up to polylo…
Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
Heng Guo, Pinyan Lu
We give fully polynomial-time approximation schemes (FPTAS) for the partition function of ferromagnetic 2-spin systems in certain parameter regimes. The threshold we obtain is almo…
Correlation Decay up to Uniqueness in Spin Systems
Liang Li, Pinyan Lu, Yitong Yin
We give a complete characterization of the two-state anti-ferromagnetic spin systems which are of strong spatial mixing on general graphs. We show that a two-state anti-ferromagnet…