@inproceedings{fox2013online,
author = {Fox, Kyle and Im, Sungjin and Kulkarni, Janardhan (Jana) and Moseley, Benjamin},
title = {Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions},
year = {2013},
month = {August},
abstract = {We consider scheduling jobs online to minimize the objective ∑  i ∈ [n] w ig(C i  − r i ), where w i is the weight of job i, r i is its release time, C i is its completion time and g is any non-decreasing convex function. Previously, it was known that the clairvoyant algorithm Highest-Density-First (HDF) is (2 + ε)-speed O(1)-competitive for this objective on a single machine for any fixed 0 < ε < 1 [1]. We show the first non-trivial results for this problem when g is not concave and the algorithm must be non-clairvoyant. More specifically, our results include:




 	
A (2 + ε)-speed O(1)-competitive non-clairovyant algorithm on a single machine for all non-decreasing convex g, matching the performance of HDF for any fixed 0 < ε < 1.

 	
A (3 + ε)-speed O(1)-competitive non-clairovyant algorithm on multiple identical machines for all non-decreasing convex g for any fixed 0 < ε < 1.




Our positive result on multiple machines is the first non-trivial one even when the algorithm is clairvoyant. Interestingly, all performance guarantees above hold for all non-decreasing convex functions g simultaneously. We supplement our positive results by showing any algorithm that is oblivious to g is not O(1)-competitive with speed less than 2 on a single machine. Further, any non-clairvoyent algorithm that knows the function g cannot be O(1)-competitive with speed less than 2–√2 on a single machine or speed less than 2−1m2−1m on m identical machines.},
publisher = {Springer Berlin Heidelberg},
url = {http://approjects.co.za/?big=en-us/research/publication/online-non-clairvoyant-scheduling-simultaneously-minimize-convex-functions/},
}