2 citations · 7 across the 12 of their papers we have counts for
5 papers · 1 filter
The Power of Amortized Recourse for Online Graph Problems
Hsiang-Hsuan Liu, Jonathan Toole-Charignon
In this work, we study online graph problems with monotone-sum objectives. We propose a general two-fold greedy algorithm that references yardstick algorithms to achieve -compet…
Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu
We present a unified framework for minimizing average completion time for many seemingly disparate online scheduling problems, such as the traveling repairperson problems (TRP), di…
A Primal-Dual Online Deterministic Algorithm for Matching with Delays
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu +1
In the Min-cost Perfect Matching with Delays (MPMD) problem, 2 m requests arrive over time at points of a metric space. An online algorithm has to connect these requests in pairs,…
P_3-Games on Chordal Bipartite Graphs
Wing-Kai Hon, Ton Kloks, Fu-Hong Liu +3
Let G=(V,E) be a connected graph. A set U subseteq V is convex if G[U] is connected and all vertices of V\U have at most one neighbor in U. Let sigma(W) denote the unique smallest…
Non-preemptive Scheduling in a Smart Grid Model and its Implications on Machine Minimization
Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong
We study a scheduling problem arising in demand response management in smart grid. Consumers send in power requests with a flexible feasible time interval during which their reques…