[2018-01-05] Mong-Jen Kao, Sinica,“Linear Programming Relaxations for Combinatorial Optimization Problems”

Title: Linear Programming Relaxations for Combinatorial Optimization Problems
Date: 2018-01-05  02:20 pm-03:30 pm
Location: R103, CSIE
Speaker: Mong-Jen Kao, Sinica.
Hosted by: Prof. DT Lee


​​Combinatorial optimization refers to finding an optimal object (configuration) from a finite set of objects. This generally includes all sorts of discrete optimization problems arising from graph theory, scheduling theory, etc.

Among the techniques that were developed to solve or approximately solve combinatorial optimization problems, linear programming provides a unifying and dominating framework that, when used properly, usually gives the best result. In this talk I will try to introduce this powerful framework by examining typical textbook problems and their linear programming formulations.


Mong-Jen Kao is a postdoc at the Institute of Information Science in Academia Sinica. He receives the B.S. degree and also his Ph.D. degree from the department of Computer Science and Information Engineering, National Taiwan University. His research interests include the design and analysis of approximation algorithms for various kinds of combinatorial optimization problems.

最後修改時間:2018-01-02 PM 4:05

cron web_use_log