8 citations · 12 across the 9 of their papers we have counts for
11 papers
Job Scheduling under Base and Additional Fees, with Applications to Mixed-Criticality Scheduling
Yi-Ting Hsieh, Mong-Jen Kao, Jhong-Yun Liu +1
We are concerned with the problem of scheduling jobs onto identical machines. Each machine has to be in operation for a prescribed time, and the objective is to minimize th…
Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics
Hyung-Chan An, Mong-Jen Kao, Changyeol Lee +1
We consider the classic correlation clustering problem in the hierarchical setting. Given a complete graph and layers of input information, where the input of each…
Improved LP-based Approximation Algorithms for Facility Location with Hard Capacities
Mong-Jen Kao
The Capacitated Facility Location (CFL), a long-standing classic problem with intriguing approximability and literature dated back to the 90s, is considered. Following the open que…
O(f) Bi-Approximation for Capacitated Covering with Hard Capacities
Mong-Jen Kao, Hai-Lun Tu, D. T. Lee
We consider capacitated vertex cover with hard capacity constraints (VC-HC) on hypergraphs. In this problem we are given a hypergraph with a maximum edge size . Each e…
Iterative Partial Rounding for Vertex Cover with Hard Capacities
Mong-Jen Kao
We provide a simple and novel algorithmic design technique, for which we call iterative partial rounding, that gives a tight rounding-based approximation for vertex cover with hard…
Competitive Design and Analysis for Machine-Minimizing Job Scheduling Problem
Mong-Jen Kao, Jian-Jia Chen, Ignaz Rutter +1
We explore the machine-minimizing job scheduling problem, which has a rich history in the line of research, under an online setting. We consider systems with arbitrary job arrival…
Optimal Time-Convex Hull under the Lp Metrics
Bang-Sin Dai, Mong-Jen Kao, D. T. Lee
We consider the problem of computing the time-convex hull of a point set under the general metric in the presence of a straight-line highway in the plane. The traveling speed…
Online Power-Managing Strategy with Hard Real-Time Guarantees
Jian-Jia Chen, Mong-Jen Kao, D. T. Lee +2
We consider the problem of online dynamic power management that provides hard real-time guarantees. In this problem, each of the given jobs is associated with an arrival time, a de…
Approximating Metrics by Tree Metrics of Small Distance-Weighted Average Stretch
Mong-Jen Kao, Der-Tsai Lee, Dorothea Wagner
We study the problem of how well a tree metric is able to preserve the sum of pairwise distances of an arbitrary metric. This problem is closely related to low-stretch metric embed…
Capacitated Domination: Constant Factor Approximation for Planar Graphs
Mong-Jen Kao, D. T. Lee
We consider the capacitated domination problem, which models a service-requirement assigning scenario and which is also a generalization of the dominating set problem. In this prob…
Approximation Algorithms for the Capacitated Domination Problem
Mong-Jen Kao, Han-Lin Chen
We consider the {\em Capacitated Domination} problem, which models a service-requirement assignment scenario and is also a generalization of the well-known {\em Dominating Set} pro…