國立清華大學資訊工程學系

Department of Computer Science

National Tsing Hua University

專題演講

SEMINAR

SPEAKER 主講人：Dr. Hsiang-Hsuan Liu (劉向瑄)

TOPIC 題　目：Optimization under Uncertainty -- Online Matching with Delays

DATE 時  間： 108年08月01日(四)下午2點至3點

地　點：台達館629教室

Abstract

Online optimization deals with various optimization problems without knowledge about the future. Furthermore, the decision cannot be undone or changed once it is made. For example, should one arrange a tight schedule even he/she cannot predict if there will be an emergency? Should some special device be bought if we do not know how often it will be used in the future? How to design the pick-up strategy of several elevators so they can work efficiently without knowing the demands from future users? Generally, in online optimization problems, some irrevocable decision is made upon seeing a current request, and it is not clear if there will be a better choice in the future. The performance of an online algorithm is measured by the competitive ratio, that is, the ratio between the cost of the online algorithm and the one of an optimal offline algorithm, which has unlimited computational resources and knows the future.

In this talk, we will go through the basic ideas of online models and then focus on the Min-cost Perfect Matching with Delays (MPMD) problem. Consider a gaming platform that hosts two-player games, such as chess, goes or scrabbles, where participants are joining in real-time, each wanting to play against another human player. The system matches players according to their known capabilities aiming at minimizing their dissimilarities: any player wants to compete against an opponent with comparable skills. A better match for a player can be found if the platform delays matching decisions as meanwhile more appropriate opponents may join the system. However, an excessive delay may also degrade the quality of experience. Therefore, a matching mechanism that runs on a gaming platform has to balance two conflicting objectives: to minimize the waiting time of any player and to minimize dissimilarities between matched players.

The problem is inherently online: a matching algorithm for the gaming platform has to react in real-time, without the knowledge about future requests (player arrivals) and make its decision irrevocably: once two requests (players) are paired, they remain paired forever.

Formally, in the MPMD problem, 2m requests arrive over time at points of a metric space. An online algorithm has to connect these requests in pairs, but a decision to match may be postponed till a more suitable matching pair is found. The goal is to eventually match all requests and minimize the joint cost of connection and the total waiting time of all requests. We present an O(m)-competitive algorithm based on linear programming. The idea is adapting the moat-growing framework, which is developed originally for (offline) constrained connectivity problems (e.g., for Steiner problems), to an online setting.

Speaker bio:

Hsiang-Hsuan Liu is currently a postdoc researcher at the Institute of Computer Science, Wroclaw University. Her research interests are in the design and analysis of algorithms for optimization problems. She focuses on designing online and approximation algorithms in various application areas, including network design, resource allocation, and scheduling problems. She has also worked on graph algorithms on special graph classes.

 聯絡人：韓永楷 教授