Constructive Quasi-Ramsey Numbers and Tournament Ranking

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.