Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
From MaRDI portal
Publication:1330796
DOI10.1007/BF01215349zbMath0811.68062MaRDI QIDQ1330796
Satish B. Rao, Bruce M. Maggs, Frank Thompson Leighton
Publication date: 11 August 1994
Published in: Combinatorica (Search for Journal in Brave)
Network design and communication in computer systems (68M10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Mathematical problems of computer architecture (68M07)
Related Items (43)
Bottleneck Congestion Games with Logarithmic Price of Anarchy ⋮ Scheduling trains with small stretch on a unidirectional line ⋮ Invited talk: Resilient distributed algorithms ⋮ Direct routing: Algorithms and complexity ⋮ The impact of local policies on the quality of packet routing in paths, trees, and rings ⋮ Scheduling Bidirectional Traffic on a Path ⋮ Atomic routing games on maximum congestion ⋮ A stochastic process on a network with connections to Laplacian systems of equations ⋮ Solving the job-shop scheduling problem optimally by dynamic programming ⋮ Scheduling on unrelated machines under tree-like precedence constraints ⋮ Low-congestion shortcuts without embedding ⋮ Routing and scheduling for energy and delay minimization in the powerdown model ⋮ Approximating call-scheduling makespan in all-optical networks ⋮ Online packet-routing in grids with bounded buffers ⋮ Efficient delay routing ⋮ Approximation algorithms for multiprocessor scheduling under uncertainty ⋮ Routing with bounded buffers and hot-potato routing in vertex-symmetric networks ⋮ Sparse Semi-Oblivious Routing: Few Random Paths Suffice ⋮ Scheduling problems in transportation networks of line topology ⋮ Oblivious Routing for Sensor Network Topologies ⋮ Scheduling Problems over Network of Machines ⋮ Universal Packet Routing with Arbitrary Bandwidths and Transit Times ⋮ Approximation Algorithms for Generalized Path Scheduling ⋮ Improved algorithms for latency minimization in wireless networks ⋮ On the benefit of supporting virtual channels in wormhole routers ⋮ [https://portal.mardi4nfdi.de/wiki/Publication:4521547 Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma] ⋮ Scheduling problems over a network of machines ⋮ On the power of randomization for job shop scheduling withk-units length tasks ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion ⋮ UNIVERSAL ROUTING AND PERFORMANCE ASSURANCE FOR DISTRIBUTED NETWORKS ⋮ Approximability of flow shop scheduling ⋮ Adaptive packet routing for bursty adversarial traffic ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ FIFO and randomized competitive packet routing games ⋮ O(log m)-approximation for the routing open shop problem ⋮ On-line and off-line preemptive two-machine job shop scheduling ⋮ Approximation algorithms for routing and call scheduling in all-optical chains and rings. ⋮ On the drift of short schedules. ⋮ Train Scheduling on a Unidirectional Path ⋮ Bounding Residence Times for Atomic Dynamic Routings ⋮ Approximation algorithms for shop scheduling problems with minsum objective ⋮ Near-optimal scheduling in the congested clique
Cites Work
This page was built for publication: Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
