Elliot Anshelevich - Publications
Last Updated: 07/27/2012

Journal Publications

• Strategic Multiway Cut and Multicut Games. (abstract)
  Elliot Anshelevich, Bugra Caskurlu, and Ameya Hate.
  Theory of Computing Systems, to appear.
  
  

  Anarchy, Stability, and Utopia: Creating Better Matchings. (abstract)

  Elliot Anshelevich, Sanmay Das and Yonatan Naamad.

  Journal of Autonomous Agents and Multi-Agent Systems, to appear.
  
  

  Exact and Approximate Equilibria for Optimal Group Network Formation. (abstract) (slides)

  Elliot Anshelevich and Bugra Caskurlu.

  Theoretical Computer Science, Volume 412, Issue 39 (September 2011), pp. 5298-5314.
  
  

  Contribution Games in Social Networks.(abstract) (slides)

  Elliot Anshelevich and Martin Hoefer.

  Algorithmica, accepted for publication.
  
  

  Terminal Backup, 3D Matching, and Covering Cubic Graphs.(abstract)

  Elliot Anshelevich and Adriana Karagiozova.

  In SIAM Journal on Computing, Volume 40, Issue 3 (2011), pp. 678-708.
  
  

  Price of Stability in Survivable Network Design. (abstract)

  Elliot Anshelevich and Bugra Caskurlu.

  In Theory of Computing Systems, Volume 49, Number 1 (July 2011), pp. 98-138.
  
  

  Strategic Network Formation through Peering and Service Agreements. (pdf) (abstract)

  Elliot Anshelevich, Bruce Shepherd, and Gordon Wilfong.

  Games and Economic Behavior, Volume 73, Issue 1, September 2011, pp. 17-38.
  
  

  Approximability of the Firefighter Problem: Computing Cuts over Time. (abstract) (slides)

  Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, and Chaitanya Swamy.

  Algorithmica, Volume 62, Issue 1 (2012), Pages 520-536.
  
  

  The Price of Stability for Network Design with Fair Cost Allocation. (pdf) (abstract)

  Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Tom Wexler, and Tim Roughgarden.

  In SIAM Journal on Computing, Volume 38, Issue 4 (November 2008), pp. 1602-1623.
  
  

  Path Decomposition under a New Cost Measure with Applications to Optical Network Design.(abstract)

  Elliot Anshelevich and Lisa Zhang.

  In ACM Transactions on Algorithms (TALG), Volume 4, Issue 1 (March 2008).
  
  

  Near-Optimal Network Design with Selfish Agents. (abstract)

  Elliot Anshelevich, Anirban Dasgupta, Eva Tardos, and Tom Wexler.

  In Theory of Computing, Volume 4 (2008), pp. 77-109.
  
  

  Stability of Load Balancing Algorithms in Dynamic Adversarial Systems.(abstract)

  Elliot Anshelevich, David Kempe, and Jon Kleinberg.

  In SIAM Journal on Computing, Volume 37, Issue 5 (January 2008), pp. 1656-1673.
  
  

Conference Proceedings

• Strategic Pricing in Next-hop Routing with Elastic Demands.(abstract)
  Elliot Anshelevich, Ameya Hate, and Koushik Kar.
  In Proc. 4th International Symposium on Algorithmic Game Theory (SAGT 2011).
  
  

  Capacity Allocation Games for Network-Coded Multicast Streaming.(abstract)

  Elliot Anshelevich, Bugra Caskurlu, Koushik Kar, and Hang Zhang.

  In Proc. 2nd International ICST Conference on Game Theory for Networks (GameNets 2011).
  
  

  A Stackelberg Strategy for Routing Flow over Time.(abstract)

  Umang Bhaskar, Lisa Fleischer, and Elliot Anshelevich.

  In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 2011).
  
  

  Strategic Multiway Cut and Multicut Games.(abstract)

  Elliot Anshelevich, Bugra Caskurlu, and Ameya Hate.

  In Proc. 8th Workshop on Approximation and Online Algorithms (WAOA 2010).
  
  

  Partition Equilibrium Always Exists in Resource Selection Games.(abstract)

  Elliot Anshelevich, Bugra Caskurlu, and Ameya Hate.

  In Proc. 3rd International Symposium on Algorithmic Game Theory (SAGT 2010).
  
  

  Contribution Games in Social Networks.(abstract) (slides)

  Elliot Anshelevich and Martin Hoefer.

  In Proc. 18th Annual European Symposium on Algorithms (ESA 2010).
  
  

  Approximations for the FireFighter Problem: Cuts over Time and Submodularity.(abstract) (slides)

  Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, and Chaitanya Swamy.

  In Proc. 20th International Symposium on Algorithms and Computation (ISAAC 2009).
  
  

  Exact and Approximate Equilibria for Optimal Group Network Formation. (abstract) (slides)

  Elliot Anshelevich and Bugra Caskurlu.

  In Proc. 17th Annual European Symposium on Algorithms (ESA 2009).
  
  

  Anarchy, Stability, and Utopia: Creating Better Matchings. (abstract)

  Elliot Anshelevich, Sanmay Das and Yonatan Naamad.

  In Proc. 2nd International Symposium on Algorithmic Game Theory (SAGT 2009).
  
  

  Equilibria in Dynamic Selfish Routing. (abstract)

  Elliot Anshelevich and Satish Ukkusuri.

  In Proc. 2nd International Symposium on Algorithmic Game Theory (SAGT 2009).
  
  

  Price of Stability in Survivable Network Design.(abstract)

  Elliot Anshelevich and Bugra Caskurlu.

  Conference version appeared in Proc. 2nd International Symposium on Algorithmic Game Theory (SAGT 2009).

  Invited to Special Issue of Theory of Computing Systems.
  
  

  Network Formation and Routing by Strategic Agents using Local Contracts. (abstract)

  Elliot Anshelevich and Gordon Wilfong.

  In Proc. 4th International Workshop On Internet And Network Economics (WINE 2008).
  
  

  On Survivable Access Network Design: Complexity and Algorithms. (abstract)

  Dahai Xu, Elliot Anshelevich, and Mung Chiang.

  In Proc. 27th IEEE Conference on Computer Communications (INFOCOM 2008).
  
  

  Terminal Backup, 3D Matching, and Covering Cubic Graphs.(abstract)

  Elliot Anshelevich and Adriana Karagiozova.

  In Proc. 39th ACM Symposium on Theory of Computing (STOC 2007).
  
  

  Strategic Network Formation through Peering and Service Agreements. (pdf) (abstract)

  Elliot Anshelevich, Bruce Shepherd, and Gordon Wilfong.

  (Older title: "Local Peering and Service Contracts in Strategic Network Formation.")

  In Proc. 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006).
  
  

  The Price of Stability for Network Design with Fair Cost Allocation. (pdf) (abstract)

  Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Tom Wexler, and Tim Roughgarden.

  In Proc. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004).
  
  

  Path Decomposition under a New Cost Measure with Applications to Optical Network Design.(abstract)

  Elliot Anshelevich and Lisa Zhang.

  In Proc. 12th Annual European Symposium on Algorithms (ESA 2004).
  
  

  Near-Optimal Network Design with Selfish Agents. (abstract)

  Elliot Anshelevich, Anirban Dasgupta, Eva Tardos, and Tom Wexler.

  In Proc. 35th ACM Symposium on Theory of Computing (STOC 2003).
  
  

  Stability of Load Balancing Algorithms in Dynamic Adversarial Systems.(abstract)

  Elliot Anshelevich, David Kempe, and Jon Kleinberg.

  In Proc. 34th ACM Symposium on Theory of Computing (STOC 2002).
  
  

  Deformable Volumes in Path Planning Applications.(abstract)

  Elliot Anshelevich, Scott Owens, Florent Lamiraux, and Lydia Kavraki.

  IEEE International Conference on Robotics and Automation (ICRA) 2000, 2290-2295.
  
  

Miscellaneous

• Pricing and Forwarding Games for Inter-domain Routing.
  Ameya Hate, Elliot Anshelevich, Koushik Kar, and Michael Usher.
  Submitted for publication.
  
  

  Matching, Cardinal Utility, and Social Welfare.(abstract)

  Elliot Anshelevich and Sanmay Das.

  Newsletter of the ACM Special Interest Group on E-commerce (SIGecom Exchanges), Volume 9.1, June 2010.
  
  

  A Competitive Strategy for Routing Flow over Time.

  Umang Bhaskar, Lisa Fleischer, and Elliot Anshelevich.

  Newsletter of the ACM Special Interest Group on E-commerce (SIGecom Exchanges), Volume 10.2, June 2011.
  
  

  Network Design and Management with Strategic Agents.(abstract)

  Elliot Anshelevich.

  Ph.D. Thesis, Cornell University, 2005.