This shows you the differences between two versions of the page.
— |
balancing_delay_and_congestion_costs_in_scheduling_and_computing_bottleneck_congestion_equilibria [2016/09/01 19:15] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | Abstract: | ||
+ | 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. |