enter search term and/or author name
We study the nondeterministic cell-probe complexity of static data structures. We introduce cell-probe proofs (CPP), a proof system for the cell-probe model, which describes verification instead of computation in the cell-probe model. We...
Tradeoffs and Average-Case Equilibria in Selfish Routing
Martin Hoefer, Alexander Souza
Article No.: 2
We study Nash equilibria in a selfish routing game on m parallel links with transmission speeds. Each player seeks to communicate a message by choosing one of the links, and each player desires to minimize his experienced transmission time...