Abstract
A constructive lower bound on the quasi-Ramsey numbers and the tournament ranking function was obtained in [S. Poljak, V. Rödl, 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 guaranteed lower bound for the linear ordering problem.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 48-63 |
| Number of pages | 16 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 12 |
| Issue number | 1 |
| DOIs | |
| State | Published - 1999 |
| Externally published | Yes |
Keywords
- Derandomization
- Discrepancy
- Linear ordering problem
- Regularity lemma
ASJC Scopus subject areas
- General Mathematics