PhD Thesis Final Defense to be held on November 27, 2018 at 13:45

The examination is open to anyone who wishes to attend (Room Γ.2.2., New ECE Building).

Thesis Title: Approximation Algorithms for Packet Routing in Networks with Reconfiguration Cost


In the modern technology based society, routing messages in packets is often used in various types of networks (optical, switching, SS/TDMA etc). This thesis is about designing efficient algorithms to schedule messages transmitted through such networks. Packet routing with reconfigution overhead is an NP-Hard problem. This research has resulted in a variety of algorithms improving past research and addressing the problem by handling the data from different angles and perspectives depending on the network and data types. Among the algorithms designed outstands the family of algorithms A-PBS(a) which includes the algorithm A-PBS(d+1) (for a=d+1) with the best and only approximation ratio strictly lower than two.

Supervisor: Foto Afrati, Retired Professor

PhD student: Timos Aslanidis