Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Lisa Fleischer:

TR05-131 | 7th November 2005
Don Coppersmith, Lisa Fleischer, Atri Rudra

Ordering by weighted number of wins gives a good ranking for weighted tournaments

We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of $5$ if the weights satisfy \textit{probability constraints}
(for any pair of vertices $u$ and $v$, $w_{uv}+w_{vu}=1$). Special cases ... more >>>

ISSN 1433-8092 | Imprint