Author name cluster

Wolfgang Bein

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

TCS Journal 2023 Journal Article

Breaking the 2-competitiveness barrier for two servers in a tree

Wolfgang Bein
Lawrence L. Larmore

A randomized on-line algorithm is given for the 2-server problem on a tree, with competitiveness less than 1. 94 against the oblivious adversary. This is the first algorithm for this problem with competitive ratio less than 2. The algorithm generalizes earlier work for the line using fractional analysis, and defines a potential in terms of isolation indices from T-theory.

Details DOI

TCS Journal 2015 Journal Article

R–LINE: A better randomized 2-server algorithm on the line

Lucas Bang
Wolfgang Bein
Lawrence L. Larmore

A randomized on-line algorithm is given for the 2-server problem on the line, with competitiveness less than 1. 901 against the oblivious adversary. This improves the previously best known competitiveness of 155 78 ≈ 1. 987 for the problem. The algorithm uses a new approach and defines a potential in terms of isolation indices from T-theory.

Details DOI

TCS Journal 2011 Journal Article

A randomized algorithm for two servers in cross polytope spaces

Wolfgang Bein
Kazuo Iwama
Jun Kawahara
Lawrence L. Larmore
James A. Oravec

It has been a long-standing open problem to determine the exact randomized competitiveness of the 2 -server problem, that is, the minimum competitiveness of any randomized online algorithm for the 2 -server problem. For deterministic algorithms the best competitive ratio that can be obtained is 2 and no randomized algorithm is known that improves this ratio for general spaces. For the line, Bartal et al. (1998) [2] give a 155 78 competitive algorithm, but their algorithm is specific to the geometry of the line. We consider here the 2 -server problem over Cross Polytope Spaces M 24. We obtain an algorithm with competitive ratio of 19 12, and show that this ratio is best possible. This algorithm gives the second non-trivial example of metric spaces with better than 2 -competitive ratio. The algorithm uses a design technique called the knowledge state technique — a method not specific to M 24.

Details DOI

TCS Journal 2009 Journal Article

Optimally competitive list batching

Wolfgang Bein
Leah Epstein
Lawrence L. Larmore
John Noga

Batching has been studied extensively in the offline case, but applications such as manufacturing or TCP acknowledgment often require online solutions. We consider online batching problems, where the order of jobs to be batched is fixed and where we seek to minimize the sum of the completion times of the jobs. We present optimally competitive online algorithms for both s -batch and p -batch problems, and we also derive results for certain naturally occurring special cases, such as the case of unit processing times.

Details DOI

TCS Journal 2008 Journal Article

A fast asymptotic approximation scheme for bin packing with rejection

Wolfgang Bein
José R. Correa
Xin Han

“Bin packing with rejection” is the following problem: Given a list of items with associated sizes and rejection costs, find a packing into unit bins of a subset of the list such that the number of bins used plus the sum of rejection costs of unpacked items is minimized. We show that bin packing with rejection can be reduced to n multiple knapsack problems and, based on techniques for the multiple knapsack problem, we give a fast asymptotic polynomial time approximation scheme, “Reject&Pack”, with time complexity O ( n O ( ϵ − 2 ) ). This improves a recent approximation scheme given by Epstein, which has time complexity O ( n O ( ( ϵ − 4 ) ϵ − 1 ) ). We also show that Reject&Pack can be extended to variable-sized bin packing with rejection and give an asymptotic polynomial time approximation scheme.

Details DOI