首页| English| 中国科学院

Approximation and Online algorithms Design Based on Linear Programs

副标题:

时间:2019-08-07  来源:

题目:           Approximation and Online algorithms Design Based on Linear Programs

报告人:      陈文彬 (广州大学)

时间地点:   2019.08.09  16:00pm  N202

摘要:          Randomized rounding is a technique for designing approximation algorithms for NP-hard optimization problems. Many combinatorial optimization problems can be represented as 0-1 integer linear programs; While 0-1 integer linear programming is NP-hard, the rational relaxations of these linear programs are solvable in polynomial time. Randomized rounding is a technique to construct a provably good solution to a 0-1 integer linear program from an optimum solution to its rational relaxation by means of a randomized algorithm.

                     The primal–dual method is a powerful algorithmic technique that has proved to be extremely useful for a wide variety of problems in the area of online algorithms.

                     In this talk, we will design a LP-based approximation algorithm for the Maximum Duo-preservation String Mapping Problem via randomized rounding method and  a Primal-Dual Online Algorithm for the k-Server Problem on Weighted HSTs.
相关附件
相关文档