Network Algorithms and Complexity
|Class Hours - Lab Hours||3 - 0|
|Lecturers||Dimitris Fotakis, Aris Pagourtzis|
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.