NDLI: On-Line Load Balancing and Network Flow

Content Provider	Springer Nature Link
Author	Phillips, S. Westbrook, J.
Abstract	In this paper we study two problems that can be viewed as on-line games on a dynamic bipartite graph. The first problem is on-line load balancing with preemption. A centralized scheduler must assign tasks to servers, processing on-line a sequence of task arrivals and departures. Each task is restricted to run on some subset of the servers. The scheduler attempts to keep the load well-balanced. If preemptive reassignments are disallowed, Azar et al. [3] proved a lower bound of Ω(n 1/2 ) on the ratio between the maximum load achieved by an on-line algorithm and the optimum off-line maximum load. We show that this ratio can be greatly reduced by an efficient scheduler using only a small amount of rescheduling. We then apply these ideas to network flow. Cheriyan and Hagerup [6] introduced an on-line game on a bipartite graph as a fundamental step in improving algorithms for computing the maximum flow in networks. They described a randomized strategy to play the game. King et al. [11] studied a modified version of this game, called ``node kill,'' and gave a deterministic strategy. We obtain an improved deterministic algorithm for the node kill game (and hence for maximum flow) in all but the sparsest graphs. The running time achieved is O(mn log m/n n+n 2 log 2+ε n) , compared with King et al.'s O(mn+n 2+ε ) . These problems combine a demand for good competitive ratios with more traditional requirements of implementation efficiency. Our solutions deal with the tradeoffs between these measures.
Starting Page	245
Ending Page	261
Page Count	17
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	21
Issue Number	3
e-ISSN	14320541
Language	English
Publisher	Springer-Verlag
Publisher Date	1998-07-01
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Improved Bounds for On-Line Load Balancing

A novel robust on-line protocol for load-balancing in structured peer-to-peer systems

FlowMate: scalable on-line flow clustering

Equilibria in load balancing games

On the Stability of Dynamic Diffusion Load Balancing

User Association for Load Balancing in Heterogeneous Cellular Networks

An OpenFlow-Based Load Balancing Strategy in SDN

Distributed Inter-BS Cooperation Aided Energy Efficient Load Balancing for Cellular Networks

Temporary Tasks Assignment Resolved

On-Line Load Balancing and Network Flow

Similar Documents

Improved Bounds for On-Line Load Balancing

A novel robust on-line protocol for load-balancing in structured peer-to-peer systems

FlowMate: scalable on-line flow clustering

Equilibria in load balancing games

On the Stability of Dynamic Diffusion Load Balancing

User Association for Load Balancing in Heterogeneous Cellular Networks

An OpenFlow-Based Load Balancing Strategy in SDN

Distributed Inter-BS Cooperation Aided Energy Efficient Load Balancing for Cellular Networks

Temporary Tasks Assignment Resolved

On-Line Load Balancing and Network Flow