41 citations · 42 across the 3 of their papers we have counts for
3 papers
cs.DS2009★ 1 cited
A Program to Determine the Exact Competitive Ratio of List s-Batching with Unit Jobs
Wolfgang Bein, Leah Epstein, Lawrence L. Larmore +1
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 w…
cs.DM2005
Random Walks with Anti-Correlated Steps
Dirk Wagner, John Noga
We conjecture the expected value of random walks with anti-correlated steps to be exactly 1. We support this conjecture with 2 plausibility arguments and experimental data. The exp…
cs.DS2005★ 41 cited
Incremental Medians via Online Bidding
Marek Chrobak, Claire Kenyon, John Noga +1
In the k-median problem we are given sets of facilities and customers, and distances between them. For a given set F of facilities, the cost of serving a customer u is the minimum…