Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Chan, Ho-Leung
Megow, Nicole
Sitters, René
van Stee, Rob

dblp
dblp
dblp
dblp

Not MPG Author(s):

Chan, Ho-Leung
Sitters, René

BibTeX cite key*:

ChMeSS12

Title

Title*:

A note on sorting buffers offline

Journal

Journal Title*:

Theoretical Computer Science

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:


Publisher's
Address:

Amsterdam

ISSN:

0304-3975

Vol, No, pp, Date

Volume*:

423

Number:


Publishing Date:

March 2012

Pages*:

11-18

Number of
VG Pages:

8

Page Start:

11

Page End:

18

Sequence Number:


DOI:

10.1016/j.tcs.2011.12.077

Note, Abstract, ©

Note:


(LaTeX) Abstract:

We consider the offline sorting buffer problem. The input is a
sequence of items of different types. All items must be processed
one by one by a server. The server is equipped with a random-access
buffer of limited capacity which can be used to rearrange items. The
problem is to design a scheduling strategy that decides upon the
order in which items from the buffer are sent to the server. Each
type change incurs unit cost, and thus, the
objective is to minimize the total number of type changes for
serving the entire sequence. This problem is motivated by various
applications in manufacturing processes and computer science, and it
has attracted significant attention in the last few years. The main
focus has been on online competitive algorithms. Surprisingly little
is known on the basic offline problem.

In this paper, we show that the sorting buffer problem with
uniform cost is NP-hard and, thus, close one of the most fundamental
questions for the offline problem. On the positive side, we give
an~$O(1)$-approximation algorithm when the scheduler is given a
buffer only slightly larger than double the original size.
We also give a dynamic programming algorithm for the special case of
buffer size two that solves the problem exactly in linear time,
improving on the standard DP which runs in cubic time.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{ChMeSS12,
AUTHOR = {Chan, Ho-Leung and Megow, Nicole and Sitters, Ren{\'e} and van Stee, Rob},
TITLE = {A note on sorting buffers offline},
JOURNAL = {Theoretical Computer Science},
PUBLISHER = {Elsevier},
YEAR = {2012},
VOLUME = {423},
PAGES = {11--18},
ADDRESS = {Amsterdam},
MONTH = {March},
ISBN = {0304-3975},
DOI = {10.1016/j.tcs.2011.12.077},
}


Entry last modified by Anja Becker, 02/06/2013
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
11/14/2012 11:46:18 AM
Revision
1.
0.


Editor
Anja Becker
Rob van Stee


Edit Date
29.01.2013 13:17:35
11/14/2012 11:46:18 AM