17 citations · 56 across the 22 of their papers we have counts for
6 papers · 1 filter
A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics
T-H. Hubert Chan, Haotian Jiang, Shaofeng H. -C. Jiang
We present a unified polynomial-time approximation scheme (PTAS) for the prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree problem (PCSTP) i…
A PTAS for the Steiner Forest Problem in Doubling Metrics
T-H. Hubert Chan, Shuguang Hu, Shaofeng H. -C. Jiang
We achieve a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner Forest Problem in doubling metrics. Before our work, a PTAS is given only for the Euclidean pl…
Online Convex Covering and Packing Problems
T-H. Hubert Chan, Zhiyi Huang, Ning Kang
We study the online convex covering problem and online convex packing problem. The (offline) convex covering problem is modeled by the following convex program: $\min_{x \in R_+^n}…
Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints
T-H. Hubert Chan, Fei Chen, Xiaowei Wu +1
Motivated by online advertisement and exchange settings, greedy randomized algorithms for the maximum matching problem have been studied, in which the algorithm makes (random) deci…
A Primal-Dual Continuous LP Method on the Multi-choice Multi-best Secretary Problem
T-H. Hubert Chan, Fei Chen
The J-choice K-best secretary problem, also known as the (J,K)-secretary problem, is a generalization of the classical secretary problem. An algorithm for the (J,K)-secretary probl…
Incubators vs Zombies: Fault-Tolerant, Short, Thin and Lanky Spanners for Doubling Metrics
T-H. Hubert Chan, Mingfei Li, Li Ning
Recently Elkin and Solomon gave a construction of spanners for doubling metrics that has constant maximum degree, hop-diameter O(log n) and lightness O(log n) (i.e., weight O(log n…