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

Don Coppersmith, Lisa Fleischer, Atri Rudra

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 >>>