Constructive quasi-Ramsey numbers and tournament ranking

Authors
Czygrinow, A Poljak, S Rodl, V
Citation
A. Czygrinow et al., Constructive quasi-Ramsey numbers and tournament ranking, SIAM J DISC, 12(1), 1999, pp. 48-63
Citations number
16
Categorie Soggetti
Engineering Mathematics
Journal title
SIAM JOURNAL ON DISCRETE MATHEMATICS
ISSN journal
08954801 → ACNP
Volume
12
Issue
1
Year of publication
1999
Pages
48 - 63
Database
ISI
SICI code
0895-4801(19990129)12:1<48:CQNATR>2.0.ZU;2-F
Abstract
A constructive lower bound on the quasi-Ramsey numbers and the tournament r anking function was obtained in [S. Poljak, V. Rodl, and J. Spencer, SIAM J . Discrete Math., (1) 1988, pp. 372-376]. We consider the weighted versions of both problems. Our method yields a polynomial time heuristic with guara nteed lower bound for the linear ordering problem.