|
|
||
|
IMADA - Department of Mathematics and Computer Science |
|
We study the maximum weight matching problem in the semi-streaming
model, and improve on the currently best one-pass algorithm due to
Zelke (STACS2008) by devising a deterministic approach whose
performance guarantee is 4.91 + epsilon. In addition, we study
preemptive online algorithms, a sub-class of one-pass algorithms
where we are only allowed to maintain a feasible matching in memory
at any point in time. All known results prior to Zelke's belong to
this sub-class. We provide a lower bound of 4.967 on the competitive
ratio of any such deterministic algorithm, and hence show that future
improvements will have to store in memory a set of edges which is not
necessarily a feasible matching. Host: Joan Boyar SDU HOME | IMADA HOME | Previous Page Daniel Merkle |