NDLI: Windows scheduling as a restricted version of bin packing

Please wait, while we are loading the content...

Windows scheduling as a restricted version of bin packing

Content Provider	ACM Digital Library
Author	Tamir, Tami Bar-noy, Amotz Ladner, Richard E.
Copyright Year	2007
Abstract	Given is a sequence of $\textit{n}$ positive integers $w_{1},w_{2},…,w_{n}$ that are associated with the items $1,2,…\textit{n},$ respectively. In the windows scheduling problem, the goal is to schedule all the items (equal-length information pages) on broadcasting channels such that the gap between two consecutive appearances of page $\textit{i}$ on any of the channels is at most $w_{i}$ slots (a slot is the transmission time of one page). In the unit-fractions bin packing problem, the goal is to pack all the items in bins of unit size where the size (width) of item $\textit{i}$ is $1/w_{i}.$ The optimization objective is to minimize the number of channels or bins. In the offline setting, the sequence is known in advance, whereas in the online setting, the items arrive in order and assignment decisions are irrevocable. Since a page requires at least $1/w_{i}$ of a channel's bandwidth, it follows that windows scheduling without migration (i.e., all broadcasts of a page must be from the same channel) is a restricted version of unit-fractions bin packing. Let $\textit{H}$ = $⌈&sum_{i==1}^{n}(1/w_{i})$ be the bandwidth lower bound on the required number of bins (channels). The best-known offline algorithm for the windows scheduling problem used $\textit{H}$ + $\textit{O}(ln$ $\textit{H})$ channels. This article presents an offline algorithm for the unit-fractions bin packing problem with at most $\textit{H}$ + 1 bins. In the online setting, this article presents algorithms for both problems with $\textit{H}$ + $\textit{O}(&sqrt;\textit{H})$ channels or bins, where the one for the unit-fractions bin packing problem is simpler. On the other hand, this article shows that already for the unit-fractions bin packing problem, any online algorithm must use at least $\textit{H}+&Omega(ln$ $\textit{H})$ bins. For instances in which the window sizes form a divisible sequence, an optimal online algorithm is presented. Finally, this article includes a new NP-hardness proof for the windows scheduling problem.
File Format	PDF
ISSN	15496325
e-ISSN	15496333
DOI	10.1145/1273340.1273344
Volume Number	3
Issue Number	3
Journal	ACM Transactions on Algorithms (TALG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-08-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Periodic scheduling Approximation algorithms Bin-packing Online algorithms
Content Type	Text
Resource Type	Article
Subject	Mathematics

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

Windows scheduling as a restricted version of bin packing (2007)

Windows scheduling as a restricted version of Bin Packing

A new upper bound 2.5545 on 2D Online Bin Packing

This side up!

The relative worst order ratio for online algorithms

Bin-packing Algorithms for Periodic Task Scheduling

Windows scheduling as a restricted version of bin packing

Heterogeneous Resource Allocation under Degree Constraints

Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing

Windows scheduling as a restricted version of bin packing

Similar Documents

Windows scheduling as a restricted version of bin packing (2007)

Windows scheduling as a restricted version of Bin Packing

A new upper bound 2.5545 on 2D Online Bin Packing

This side up!

The relative worst order ratio for online algorithms

Bin-packing Algorithms for Periodic Task Scheduling

Windows scheduling as a restricted version of bin packing

Heterogeneous Resource Allocation under Degree Constraints

Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing

Windows scheduling as a restricted version of bin packing