Parallel Scheduling Problems in CDMA Wireless Networks

allow multiple codes (or channels)
to be allocated to a single user, where each code can
support multiple data rates.
Providing fine-grained QoS to users in such networks poses the two
dimensional challenge
of assigning both power (rate) and codes for every user.


We abstract general downlink scheduling problems
We attempt to optimize the maximum response time of jobs.
We present provable results
on the algorithmic complexity of these scheduling
problems. In particular, we are able to provide very simple, online
algorithms for approximating the optimal maximum
response time. This relies on resource augmented competitive
analysis.

Joint work with Luca Becchetti, Suhas Digavi,
Alberto Marchetti-Spaccamela, S. Muthukrishnan,
Thiaga Nandagopal and Andrea Vitaletti