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.