On the performance of on-line algorithms for partition problems

Ulrich Faigle, Walter Kern, György Turan

Research output: Contribution to journalArticleAcademicpeer-review

77 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 languageEnglish
Pages (from-to)107-119
Number of pages13
JournalActa cybernetica
Volume9
Issue number2
Publication statusPublished - 1989

Keywords

  • IR-98373
  • METIS-140479

Fingerprint Dive into the research topics of 'On the performance of on-line algorithms for partition problems'. Together they form a unique fingerprint.

  • Cite this