Online algorithms for combinatorial optimization problems

Abstract

I focus my research on online algorithms. An online algorithm is one that can handle input that comes piece-by-piece and is only partially known at first.

The online covering problem and the online packing problem are both classic problems in the field of online algorithms. In the online covering problem, the objective function is given in advance, and constraints come online; while in the online packing problem, part of its objective function comes online. We generalize the objective functions for both problems, and propose primal dual algorithms for these generalized settings, both of which are asymptotically optimal.

We study the online submodular maximization problem with free disposal under two kinds of matroid constraints, namely uniform matroid and partition matroid. Elements from some ground set arrive one by one, and upon arrival of each element, the algorithm must choose whether to accept it or not. The algorithm can remove any element at any time, but any element rejected or removed by the algorithm cannot be accepted any more. In addition, the solution given by the algorithm must be feasible all the time, that is, independent in the given matroid constraint. We improve the performance ratio and hardness for various settings of this problem.

In the online makespan minimization problem, each job comes online with its release time and processing time, and all machines are identical. The objective is to minimize the makespan. When there are two machines, a tight ratio of $1.382$ has been found. An open question is left whether the ratio can be improved with the help of ``restart''. We solve this open question, and also find an algorithm with restart that improves the ratio when there are more than two machines.