On-line routing of virtual circuits with applications to load balancing and machine scheduling
From MaRDI portal
Publication:4376979
DOI10.1145/258128.258201zbMath0890.68014OpenAlexW2156867662MaRDI QIDQ4376979
James Aspnes, Orli Waarts, Yossi Azar, Serge A. Plotkin, Amos Fiat
Publication date: 17 February 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1997-44/
Network design and communication in computer systems (68M10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
A survey on makespan minimization in semi-online environments, The shortest first coordination mechanism for a scheduling game with parallel-batching machines, On-line service scheduling, On designing truthful mechanisms for online scheduling, Optimal Coordination Mechanisms for Unrelated Machine Scheduling, Efficient coordination mechanisms for unrelated machine scheduling, A poly-log competitive posted-price algorithm for online metrical matching on a spider, Better Algorithms for Online Bin Stretching, Worst-case Nash equilibria in restricted routing, Online load balancing with general reassignment cost, Approximation and online algorithms for multidimensional bin packing: a survey, Parallel load balancing on constrained client-server topologies, iGreen: green scheduling for peak demand minimization, ONLINE SCHEDULING OF MIXED CPU-GPU JOBS, Rejecting jobs to minimize load and maximum flow-time, Coordination mechanisms for parallel machine scheduling, A two-phase algorithm for bin stretching with stretching factor 1.5, Online algorithms for scheduling with machine activation cost on two uniform machines, Competitive and deterministic embeddings of virtual networks, Fair online load balancing, Lower bounds for online makespan minimization on a small number of related machines, Smoothed performance guarantees for local search, Configuration balancing for stochastic requests, Well-behaved online load balancing against strategic jobs, Coordination mechanisms with hybrid local policies, Parallel solutions for preemptive makespan scheduling on two identical machines, Strategic Scheduling Games: Equilibria and Efficiency, Weighted packet selection for rechargeable links in cryptocurrency networks: complexity and approximation, A Preemptive Algorithm for Maximizing Disjoint Paths on Trees, Weighted packet selection for rechargeable links in cryptocurrency networks: complexity and approximation, Online and semi-online hierarchical scheduling for load balancing on uniform machines, Online bin stretching with three bins, Non-clairvoyant scheduling games, Inefficiency of Nash equilibria with parallel processing policy, Tight Bounds for Online Vector Scheduling, Online scheduling with rejection and withdrawal, Approximate strong equilibria in job scheduling games with two uniformly related machines, Preemptive scheduling on a small number of hierarchical machines, The hierarchical model for load balancing on two machines, Optimal on-line algorithms to minimize makespan on two machines with resource augmentation, Fast approximation of minimum multicast congestion – Implementation VERSUS Theory, Robust algorithms for preemptive scheduling, A lower bound for on-line scheduling on uniformly related machines, Performance of service policies in a specialized service system with parallel servers, Performance guarantees for scheduling algorithms under perturbed machine speeds, Online Makespan Scheduling with Job Migration on Uniform Machines, A coordination mechanism for a scheduling game with parallel-batching machines, Deterministic monotone algorithms for scheduling on related machines, Online unit clustering: Variations on a theme, Online Scheduling on a CPU-GPU Cluster, A preemptive algorithm for maximizing disjoint paths on trees, Randomized on-line scheduling on two uniform machines, Unnamed Item, Exponential penalty function control of loss networks, Worst-case analysis for on-line service policies, Price of anarchy in parallel processing, On-line load balancing of temporary tasks revisited, A Coordination Mechanism for a Scheduling Game with Uniform-Batching Machines, Optimal oblivious routing in polynomial time, Scheduling of online compute-intensive synchronized jobs on high performance virtual clusters, Online scheduling of jobs with favorite machines, Decentralized utilitarian mechanisms for scheduling games, On-line path computation and function placement in SDNs, Hallucination Helps: Energy Efficient Virtual Circuit Routing, Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs, Coordination mechanisms for selfish scheduling, Multicast Routing and Design of Sparse Connectors, Variable sized online interval coloring with bandwidth, Improved price of anarchy for machine scheduling games with coordination mechanisms, Online scheduling with general machine cost functions, Randomized algorithms for online bounded bidding, Priority algorithms for the subset-sum problem, Online makespan scheduling with job migration on uniform machines, Online scheduling of moldable parallel tasks, Scheduling MapReduce jobs on identical and unrelated processors, Optimal and online preemptive scheduling on uniformly related machines, Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing, Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming, New algorithms for related machines with temporary jobs., Minimum Congestion Mapping in a Cloud, A lower bound on deterministic online algorithms for scheduling on related machines without preemption, A nonmonotone analysis with the primal-dual approach: online routing of virtual circuits with unknown durations, A Nonmonotone Analysis with the Primal-Dual Approach: Online Routing of Virtual Circuits with Unknown Durations, How to allocate goods in an online market?
