SODA Conference 2014 Conference Paper
Streaming Balanced Graph Partitioning Algorithms for Random Graphs
- Isabelle Stanton
Author name cluster
Isabelle Stanton
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
2 papers
2 author rows
Possible papers
2IJCAI Conference 2011 Conference Paper
Rigging Tournament Brackets for Weaker Players
- Isabelle Stanton
- Virginia Vassilevska Williams
Consider the following problem in game manipulation. A tournament designer who has full knowledge of the match outcomes between any possible pair of players would like to create a bracket for a balanced single-elimination tournament so that their favorite player will win. Although this problem has been studied in the areas of voting and tournament manipulation, it is still unknown whether it can be solved in polynomial time. We focus on identifying several general cases for which the tournament can always be rigged efficiently so that the given player wins. We give constructive proofs that, under some natural assumptions, if a player is ranked among the top K players, then one can efficiently rig the tournament for thegiven player, even when K is as large as 19% of the players.