Arrow Research search

Author name cluster

An Zhu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers
2 author rows

Possible papers

7

TCS Journal 2004 Journal Article

Combining request scheduling with web caching

  • Tomás Feder
  • Rajeev Motwani
  • Rina Panigrahy
  • Steve Seiden
  • Rob van Stee
  • An Zhu

We extend the classic paging model by allowing reordering of requests under the constraint that a request is delayed by no longer than a predetermined number of time steps. We first give a dynamic programming algorithm to solve the offline case. Then we give tight bounds on competitive ratios for the online case. For caches of size k, we obtain bounds of k+O(1) for deterministic algorithms and Θ(log k) for randomized algorithms. We also give bounds for the case where either the online or the offline algorithm can reorder the requests, but not both. Finally, we extend our analysis to the case where pages have different sizes.

Details DOI

FOCS Conference 2003 Conference Paper

Switch Scheduling via Randomized Edge Coloring

  • Gagan Aggarwal
  • Rajeev Motwani 0001
  • Devavrat Shah
  • An Zhu

The essence of an Internet router is an n /spl times/ n switch which routes packets from input to output ports. Such a switch can be viewed as a bipartite graph with the input and output ports as the two vertex sets. Packets arriving at input port i and destined for output port j can be modeled as an edge from i to j. Current switch scheduling algorithms view the routing of packets at each time step as a selection of a bipartite matching. We take the view that the switch scheduling problem across a sequence of time-steps is an instance of the edge coloring problem for a bipartite multigraph. Implementation considerations lead us to seek edge coloring algorithms for bipartite multigraphs that are fast, decentralized, and online. We present a randomized algorithm which has the desired properties, and uses only a near-optimal /spl Delta/ + o(/spl Delta/) colors on dense bipartite graphs arising in the context of switch scheduling. This algorithm extends to non-bipartite graphs as well. It leads to a novel switch scheduling algorithm which, for stochastic online edge arrivals, is stable, i. e. the queue length at each input port is bounded at all times. We note that this is the first decentralized switch scheduling algorithm that is also guaranteed to be stable.

Details

STOC Conference 2001 Conference Paper

Algorithms for minimizing weighted flow time

  • Chandra Chekuri
  • Sanjeev Khanna
  • An Zhu

We study the problem of minimizing weighted flow time on a single machine in the preemptive setting. We present an O(\log^2 P) -competitive semi-online algorithm where P is the ratio of the maximum and minimum processing times of jobs in the system. In the offline setting we show that a (2+\eps) -approximation is achievable in quasi-polynomial time. These are the first non-trivial results for the weighted versions of minimizing flow time. For multiple machines we show that no competitive randomized online algorithm exists for weighted flow time. We also present an improved online algorithm for minimizing total stretch (a special case of weighted flow time) on multiple machines.

Details
v2026.09.13