5 papers
Minimum Partition of Polygons under Width and Cut Constraints
Jaehoon Chung, Kazuo Iwama, Chung-Shou Liao +1
We study the problem of partitioning a polygon into the minimum number of subpolygons using cuts in predetermined directions such that each resulting subpolygon satisfies a given w…
Improving the Bounds of the Online Dynamic Power Management Problem
Ya-Chun Liang, Kazuo Iwama, Chung-Shou Liao
We investigate the {\em power-down mechanism} which decides when a machine transitions between states such that the total energy consumption, characterized by execution cost, idle…
Tight Competitive Analyses of Online Car-sharing Problems
Ya-Chun Liang, Kuan-Yun Lai, Ho-Lin Chen +1
The car-sharing problem, proposed by Luo, Erlebach and Xu in 2018, mainly focuses on an online model in which there are two locations: 0 and 1, and total cars. Each request whi…
Link Delay Estimation Using Sparse Recovery for Dynamic Network Tomography
Hao-Ting Wei, Sung-Hsien Hsieh, Wen-Liang Hwang +2
When the scale of communication networks has been growing rapidly in the past decades, it becomes a critical challenge to extract fast and accurate estimation of key state paramete…
An -Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity
Hao-Ting Wei, Wing-Kai Hon, Paul Horn +2
This study considers the (soft) capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intens…