Treffer: A Program to Determine the Exact Competitive Ratio of List s-Batching with Unit Jobs

Title:
A Program to Determine the Exact Competitive Ratio of List s-Batching with Unit Jobs
Authors:
Bein, Wolfgang, Epstein, Leah, Larmore, Lawrence L., Noga, John
Publication Year:
2009
Collection:
Computer Science
Subject Terms:
Computer Science - Data Structures and Algorithms, F.2, I.2.2
Document Type:
Report Working Paper
Access URL:
http://arxiv.org/abs/0904.1002
Accession Number:
edsarx.0904.1002
Database:
arXiv

Weitere Informationen

We consider the online list s-batch problem, where all the jobs have processing time 1 and we seek to minimize the sum of the completion times of the jobs. We give a Java program which is used to verify that the competitiveness of this problem is 619/583.