Explanipedia

On the FirstFit Algorithm for Online Unit-Interval Coloring Open

Bob Krekelberg, Hsiang-Hsuan Liu · 2025

In this paper, we study the performance of the FirstFit algorithm for the online unit-length intervals coloring problem where the intervals can be either open or closed, which serves a further investigation towards the actual performance o…

Instance complexity of Boolean functions Open

Hsiang-Hsuan Liu, Nikhil S. Mande · 2023

In the area of query complexity of Boolean functions, the most widely studied cost measure of an algorithm is the worst-case number of queries made by it on an input. Motivated by the most natural cost measure studied in online algorithms,…

The Power of Amortized Recourse for Online Graph Problems Open

Hsiang-Hsuan Liu, Jonathan Toole-Charignon · 2022

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 $t$-competitiveness while incurring at most $\frac{w_{\text{max}}\cdo…

Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times Open

Marcin Bieńkowski, Artur Kraska, Hsiang-Hsuan Liu · 2021

We present a unified framework for minimizing average completion time for many seemingly disparate online scheduling problems, such as the traveling repairperson problems (TRP), dial-a-ride problems (DARP), and scheduling on unrelated mach…

Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times. Open

Marcin Bieńkowski, Artur Kraska, Hsiang-Hsuan Liu · 2021

We present a unified framework for minimizing average completion time for many seemingly disparate online scheduling problems, such as the traveling repairperson problems (TRP), dial-a-ride problems (DARP), and scheduling on unrelated mach…

A note on the geodetic number and the Steiner number of AT-free graphs Open

Wing-Kai Hon, Ton Kloks, Hsiang-Hsuan Liu, Hung-Lung Wang, Yue-Li Wang · 2020

Complexity and online algorithms for minimum skyline coloring of intervals Open

Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, Prudence W. H. Wong , et al. · 2019

An Improved Online Algorithm for the Traveling Repairperson Problem on a Line Open

Marcin Bieńkowski, Hsiang-Hsuan Liu · 2019

In the online variant of the traveling repairperson problem (TRP), requests arrive in time at points of a metric space X and must be eventually visited by a server. The server starts at a designated point of X and travels at most at unit s…

A Primal-Dual Online Deterministic Algorithm for Matching with Delays Open

Marcin Bieńkowski, Artur Kraska, Hsiang-Hsuan Liu, Paweł Schmidt · 2018

Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals Open

Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, Prudence W. H. Wong , et al. · 2017

P_3-Games on Chordal Bipartite Graphs Open

Wing-Kai Hon, Ton Kloks, Fu-Hong Liu, Hsiang-Hsuan Liu, Tao-Ming Wang , et al. · 2016

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 convex set that contains W subseteq V. Two players play the…

Convex Independence in Permutation Graphs Open

Wing-Kai Hon, Ton Kloks, Fu-Hong Liu, Hsiang-Hsuan Liu · 2016

A set C of vertices of a graph is P_3-convex if every vertex outside C has at most one neighbor in C. The convex hull σ(A) of a set A is the smallest P_3-convex set that contains A. A set M is convexly independent if for every vertex x \in…

P_3-Games Open

Wing-Kai Hon, Ton Kloks, Fu-Hong Liu, Hsiang-Hsuan Liu, Tao-Ming Wang · 2016

Without further ado, we present the P_3-game. The P_3-game is decidable for elementary classes of graphs such as paths and cycles. From an algorithmic point of view, the connected P_3-game is fascinating. We show that the connected P_3-gam…

P_3-Games Open

Wing-Kai Hon, Ton Kloks, Fu-Hong Liu, Hsiang-Hsuan Liu, Tao-Ming Wang · 2016

Without further ado, we present the P_3-game. The P_3-game is decidable for elementary classes of graphs such as paths and cycles. From an algorithmic point of view, the connected P_3-game is fascinating. We show that the connected P_3-gam…

On the Grundy number of Cameron graphs Open

Wing-Kai Hon, Ton Kloks, Fu-Hong Liu, Hsiang-Hsuan Liu, Tao-Ming Wang · 2016

The Grundy number of a graph is the maximal number of colors attained by a first-fit coloring of the graph. The class of Cameron graphs is the Seidel switching class of cographs. In this paper we show that the Grundy number is computable i…

Optimal Nonpreemptive Scheduling in a Smart Grid Model Open

Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong · 2016

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 requests can be served. The grid controller, upon receiving power…

Non-preemptive Scheduling in a Smart Grid Model and its Implications on Machine Minimization Open

Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong · 2016

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 requests can be served. The grid controller, upon receiving power…

Optimal Nonpreemptive Scheduling in a Smart Grid Model Open

Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong · 2016

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 requests can be served. The grid controller, upon receiving power…

Rainbow Domination and Related Problems on Some Classes of Perfect Graphs Open

Wing-Kai Hon, Ton Kloks, Hsiang-Hsuan Liu, Hung Lung Wang · 2016

Flood-it on AT-Free Graphs Open

Wing-Kai Hon, Ton Kloks, Fu-Hong Liu, Hsiang-Hsuan Liu, Hung‐Lung Wang · 2015

Solitaire {\sc Flood-it}, or {\sc Honey-Bee}, is a game played on a colored graph. The player resides in a source vertex. Originally his territory is the maximal connected, monochromatic subgraph that contains the source. A move consists o…

Convexities in Some Special Graph Classes ---New Results in AT-free Graphs and Beyond Open

Wing-Kai Hon, Ton Kloks, Hsiang-Hsuan Liu, Hung‐Lung Wang, Yue-Li Wang · 2015

We study convexity properties of graphs. In this paper we present a linear-time algorithm for the geodetic number in tree-cographs. Settling a 10-year-old conjecture, we prove that the Steiner number is at least the geodetic number in AT-f…

Hsiang-Hsuan Liu YOU? Author Swipe