Combinatorial Optimization Problems With Reverse Objective

In this paper we study several variants of the reverse objective combinatorial op-timization problems, including the lazy bureaucrat scheduling problem, the maximumresource bin packing problem, and the lazy bin covering problem etc. These problemsstudy the traditional scheduling/bin packing problem in another point. Such inquiriesoften lead to a better understanding of the structure and algorithmic complexity of theoriginal optimization problem, and give rise to a rich set of new questions that ex-plore the distinction between maximization and minimization in computing optimalsolutions. The thesis is split in six chapters. In Chapter 1 we first introduce some pre-liminary concepts related to algorithms and complexity theory, and the background ofmodels considered in this thesis.In Chapter 2, we survey the relevant results on the lazy bureaucrat schedulingproblem and the maximum resource bin packing problem. Then we present the mainresults of this thesis.In Chapter 3, we consider the lazy bureaucrat scheduling problem. We focus onthe case where all the jobs share a common deadline, such a problem is denoted asCD-LBSP. As for the off-line case, we first show that the worst-case ratio of the algo-rithm SJF (Shortest Job First) is two under the objective function [min-time-spent], andthus answer an open question posed by Esfahbod et al. [23]. We further present twopolynomial time approximation schemes A_k and B_k both having worst-case ratio of1+1/k, for any given integer k＞0, under the objective function of[min-makespan]and [min-time-spent] respectively. Finally, we prove that the problem CD-LBSP re-mains NP-hard under several objective functions, even if all jobs share the same releasetime.We also consider the online case of CD-LBSP. We give an optimal online algo-rithm A with the competitive ratio of (5^1/2+1)/2 for the objective function[min-makespan]and [min-time-spent].In Chapter 4, we present the computational complexity proofs for the lazy bin cov-eting problem, the restricted open-end bin packing problem, and especially the maxi-mum resource bin packing problem, which was an open problem posed in [12; 13]. Wealso give the correspondingly best possible algorithms for these problems. In Chapter 5, we study the procrastinator scheduling problem. We present anoptimal off-line polynomial time algorithm LRTB⁺ under the objective of [min-tirae-spent], for the model with a more general job speed, function f_i(t)=m_i(t-r_i)+v_i,where v_i is the release speed of job i. We also explore on the maximum stretch ratio inonline case, we prove that 4 is best possible forα-Delay algorithms.Finally, in Chapter 5 we present a summary of our results, and point out somefuture works in these areas.