User Tools

Site Tools



This shows you the differences between two versions of the page.

Link to this comparison view

balancing_delay_and_congestion_costs_in_scheduling_and_computing_bottleneck_congestion_equilibria [2016/09/01 19:15] (current)
Line 1: Line 1:
 +We consider the problem of minimum cost scheduling of an arbitrary
 +sequence of packet arrivals over a given time frame where the cost of
 +transmission during a slot is the sum of an arbitrary function of the
 +congestion (number of packets transmitted) during that slot and the
 +delay incurred by these packets. ​ This problem could arise in various
 +contexts such as wireless link transmissions where both congestion costs
 +and scheduling delays must be balanced as well as in transactional memory
 +systems where one can complete a transaction during a slot by paying a
 +cost proportional to the number of interfering transactions during that
 +slot (the congestion) or defer by some slots and try again. We find
 +the offline optimal solution to this problem given the exact sequence
 +of packet arrivals and then develop algorithms with constant factor
 +competitive ratio for the online version of the problem in which the
 +sequence of packet arrivals is unknown. For the second part of the talk,
 +we consider the problem of computing bottleneck congestion equilibria in
 +networks. This problem has been shown to be PLS complete and we describe
 +an algorithm for finding logN approximate equilibra.
 +Bio: Rajgopal Kannan is a Professor in the Computer Science Department
 +at Louisiana State University. He obtained his PhD from the University of
 +Denver and a B.Tech from IIT-Bombay. His areas of interest are in wireless
 +network algorithms, game-theory and cybersecurity. He is currently on
 +sabbatical at the ANRG group at USC with Prof. Bhaskar Krishnamachari.
balancing_delay_and_congestion_costs_in_scheduling_and_computing_bottleneck_congestion_equilibria.txt ยท Last modified: 2016/09/01 19:15 (external edit)