On the performance of on-line algorithms for partition problems

Ulrich Faigle; Walter  Kern; György Turan

doi:10.5555/71777.71779

On the performance of on-line algorithms for partition problems

Ulrich Faigle, Walter Kern, György Turan

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

191 Downloads (Pure)

Abstract

We consider the performance of the greedy algorithm and of on-line algorithms for partition problems in combinatorial optimization. After surveying known resuls we give bounds for matroid and graph partitioning, and discuss the power of non-adaptive adversaries for proving lower bounds.

Original language	English
Pages (from-to)	107-119
Number of pages	13
Journal	Acta cybernetica
Volume	9
Issue number	2
DOIs	https://doi.org/10.5555/71777.71779
Publication status	Published - 1989

Access to Document

10.5555/71777.71779

ArticleFinal published version, 871 KB

Cite this

@article{a5c3ea9b245b4e1d98cbb8d7d93ffa65,

title = "On the performance of on-line algorithms for partition problems",

abstract = "We consider the performance of the greedy algorithm and of on-line algorithms for partition problems in combinatorial optimization. After surveying known resuls we give bounds for matroid and graph partitioning, and discuss the power of non-adaptive adversaries for proving lower bounds.",

author = "Ulrich Faigle and Walter Kern and Gy{\"o}rgy Turan",

year = "1989",

doi = "10.5555/71777.71779",

language = "English",

volume = "9",

pages = "107--119",

journal = "Acta cybernetica",

issn = "0324-721X",

publisher = "University of Szeged",

number = "2",

}

TY - JOUR

T1 - On the performance of on-line algorithms for partition problems

AU - Faigle, Ulrich

AU - Kern, Walter

AU - Turan, György

PY - 1989

Y1 - 1989

N2 - We consider the performance of the greedy algorithm and of on-line algorithms for partition problems in combinatorial optimization. After surveying known resuls we give bounds for matroid and graph partitioning, and discuss the power of non-adaptive adversaries for proving lower bounds.

AB - We consider the performance of the greedy algorithm and of on-line algorithms for partition problems in combinatorial optimization. After surveying known resuls we give bounds for matroid and graph partitioning, and discuss the power of non-adaptive adversaries for proving lower bounds.

U2 - 10.5555/71777.71779

DO - 10.5555/71777.71779

M3 - Article

SN - 0324-721X

VL - 9

SP - 107

EP - 119

JO - Acta cybernetica

JF - Acta cybernetica

IS - 2

ER -