Network Algorithms and Complexity
| Code | 446 |
|---|---|
| Semester | Spring |
| Class Hours - Lab Hours | 3 - 0 |
| Lecturers | Dimitris Fotakis, Aris Pagourtzis, Theodora Souliou (T & R Associates) |
| Links | Course's Website |
Description
Theoretical foundations of network problems. Computational complexity and approximability of relevant graph-theoretic problems: Vertex Cover, Traveling Salesman Problem, Steiner tree, Maximum Flow, Matching, Edge Coloring, Multicommodity Flow, Facility Location, Multicut, k-Center, Clustering, Scheduling. Distributed networks: leader election, broadcast, secret sharing, Byzantine agreement. Communication protocols for wireless ad hoc networks. Optical networks: routing and wavelength assignment, multi-fiber networks. Routing protocols. Selfish routing, "price of anarchy", Nash equilibria, auctions. Autonomous agents: rendezvous, coordination, explorations, fault discovery, navigation.