Constructive quasi-Ramsey numbers and tournament ranking

被引：21

作者：

Czygrinow, A ^{[1
]}

Poljak, S ^{[1
]}

Rödl, V ^{[1
]}

机构：

[1] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 USA

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1999年 / 12卷 / 01期

关键词：

discrepancy; linear ordering problem; derandomization; regularity lemma;

D O I：

10.1137/S0895480197318301

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A constructive lower bound on the quasi-Ramsey numbers and the tournament ranking 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 guaranteed lower bound for the linear ordering problem.

引用

页码：48 / 63

页数：16

共 16 条

[1] THE ALGORITHMIC ASPECTS OF THE REGULARITY LEMMA [J].

ALON, N ;

DUKE, RA ;

LEFMANN, H ;

RODL, V ;

YUSTER, R .

JOURNAL OF ALGORITHMS, 1994, 16 (01) :80-109

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3]

CZYGRINOW A, 1996, LINEAR ORDERING PROB

[4]

DELAVEGA WF, 1983, J COMB THEORY B, V35, P328

[5] A FAST APPROXIMATION ALGORITHM FOR COMPUTING THE FREQUENCIES OF SUBGRAPHS IN A GIVEN GRAPH [J].

DUKE, RA ;

LEFMANN, H ;

RODL, V .

SIAM JOURNAL ON COMPUTING, 1995, 24 (03) :598-620

[6]

ERIDOS P, 1974, PROBABILISTIC METHOD

[7] The regularity Lemma and approximation schemes for dense problems [J].

Frieze, A ;

Kannan, R .

37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :12-20

[8]

FRIEZE A, 1997, UNPUB QUICK APPROXIM

[9]

Goemans M. X., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P422, DOI 10.1145/195058.195216

[10] A CUTTING PLANE ALGORITHM FOR THE LINEAR ORDERING PROBLEM [J].

GROTSCHEL, M ;

JUNGER, M ;

REINELT, G .

OPERATIONS RESEARCH, 1984, 32 (06) :1195-1220

← 1 2 →