Research Interests:
Algorithms and theoretical computer science, especially algorithms for large
decentralized networks, including networks with strategic agents. Particular interests include: network design problems,
algorithmic game theory, local and decentralized routing
algorithms, approximation algorithms, graph algorithms, and information propagation in both social and computer networks.
See my Publications for more info.
Short Bio:
2006-Present: Assistant Professor at RPI
2005-2006: Postdoc, Princeton University (with Moses Charikar)
2000-2005: Ph.D., Cornell University (with Jon Kleinberg)
1996-2000: Comp.Sci. and Math major, Rice University
See my Curriculum Vitae for more info.
Teaching:
Office Hours - by appointment only
Spring 2009: CSCI-4020, Computer Algorithms
Spring 2009: CSCI-6963, Algorithmic Game Theory
Spring 2008, 2007: CSCI-4020, Computer Algorithms
Fall 2007, 2006: CSCI-6964, Advanced Algorithm
Design
Links:
RPI Theory Group
RPI Theory Seminar schedule (Wed 11am, in Carnegie 113)
Current PhD Students:
Bugra Caskurlu
Ameya Hate
Some Publications:
- E. Anshelevich, A. Karagiozova. Terminal Backup, 3D Matching, and Covering Cubic Graphs. In STOC 2007.
We define a nontrivial extension of non-bipartite min-cost matching called Simplex Matching, and show how to solve it in polynomial time. While interesting in its own right, its main value lies in many (seemingly very different) problems that can be solved using our algorithm. For example, in a Steiner Forest setting, it can be used to find the cheapest forest with at least 2 terminals in every component. The algorithm we provide is relatively simple to understand and implement, but difficult to prove correct. In the process of this proof we show some powerful new results about covering cubic graphs with simple combinatorial objects.
- E. Anshelevich, B. Shepherd, G. Wilfong. Strategic Network Formation through Peering and Service Agreements. In FOCS 2006. (pdf) (Older title: "Local Peering and Service Contracts in Strategic Network Formation.")
We introduce a noncooperative game in an effort to understand business relationships between entities (enterprises, ISPs, residential customers etc.) in the Internet. Connection contracts are local (ie bilateral) between two entities and may either be of a peer-peer or a customer-provider variety. Entities bid (or demand payment) for the formation of these contracts, and in the resulting network some traffic is routed and other traffic dropped; providers may incur a penalty if their customer's traffic is dropped. Stable solutions to this game have some interesting properties. We consider the structure of such solutions, as well as how to induce good stable solutions given a limited budget.
- E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, T. Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation. In FOCS 2004. (pdf)
We study the ratio of the best Nash equilibrium with the centralized optimum (the price of stability) in a network design context where independent agents wish to connect certain nodes. The best Nash equilibrium solution has a natural meaning of stability in this context -- it is the optimal solution that can be proposed from which no user will "defect". We show that if the edge cost allocation is done using a Shapley value fair division scheme, then the price of stability is at most O(log k), where k is the number of agents, and that a good Nash can be achieved via best-response dynamics. We also discuss and extend our results to many more general models, such as the case where the network has latencies.
- E. Anshelevich, L. Zhang. Path Decomposition under a New Cost Measure with Applications to Optical Network Design. In Proc. 12th Annual European Symposium on Algorithms (ESA 2004).© Springer-Verlag
We consider a network design problem with a novel yet simple cost function. The underlying network must be partitioned into disjoint paths, and the cost of a connection is the number of these paths that the connection path intersects. We give a 2-approximation algorithm in the case that the connection routes are fixed, and show an optimal algorithm for that case with maximal network degree 3. For the case where both the path partition and the connection paths must be optimized, we give a log-approximation in the general case and a 3/2-approximation for the ring topology.
- E. Anshelevich, A. Dasgupta, E. Tardos, T. Wexler.
Near-Optimal Network Design with Selfish Agents.
Proc. 35th ACM Symposium on Theory of Computing, 2003.
We study a simple network design game that models how independent selfish agents can build or maintain a large network. We show that in a restricted context, we can force these agents into a stable solution which is no worse than the centralized optimum. We also demonstrate that in a more general context, there is always an approximately stable solution which is no worse than the centralized optimum. Finally, we give poly-time algorithms to find these stable solutions.
- E. Anshelevich, D. Kempe, J. Kleinberg.
Stability of Load Balancing Algorithms in Dynamic Adversarial Systems.
Proc. 34th ACM Symposium on Theory of Computing, 2002.
We study the load balancing and packet routing problems in a dynamic online setting, where an adversary can insert and remove jobs or packets. We give simple proofs of stability for a natural distributed algorithm against rate-1 adversaries, for load balancing with up to 2 commodities, and packet routing with a single sink. A main contribution of the paper is a new proof technique for stability proofs.
