File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A note on sorting buffers offline

TitleA note on sorting buffers offline
Authors
KeywordsApproximation Algorithm
Buffer Sorting
Np-Hard
Resource Augmentation
Issue Date2012
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2012, v. 423, p. 11-18 How to Cite?
AbstractWe 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 sketch a fast dynamic programming algorithm for the special case of buffer size 2. © 2011 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/152493
ISSN
2015 Impact Factor: 0.643
2015 SCImago Journal Rankings: 0.720
ISI Accession Number ID
Funding AgencyGrant Number
German Research Foundation (DFG)STE 1727/3-2
Funding Information:

The fourth author's research was supported by the German Research Foundation (DFG) under grant no. STE 1727/3-2.

References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_US
dc.contributor.authorMegow, Nen_US
dc.contributor.authorSitters, Ren_US
dc.contributor.authorVan Stee, Ren_US
dc.date.accessioned2012-06-26T06:39:38Z-
dc.date.available2012-06-26T06:39:38Z-
dc.date.issued2012en_US
dc.identifier.citationTheoretical Computer Science, 2012, v. 423, p. 11-18en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://hdl.handle.net/10722/152493-
dc.description.abstractWe 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 sketch a fast dynamic programming algorithm for the special case of buffer size 2. © 2011 Elsevier B.V. All rights reserved.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_US
dc.relation.ispartofTheoretical Computer Scienceen_US
dc.subjectApproximation Algorithmen_US
dc.subjectBuffer Sortingen_US
dc.subjectNp-Harden_US
dc.subjectResource Augmentationen_US
dc.titleA note on sorting buffers offlineen_US
dc.typeArticleen_US
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_US
dc.identifier.authorityChan, HL=rp01310en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/j.tcs.2011.12.077en_US
dc.identifier.scopuseid_2-s2.0-84857042070en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-84857042070&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume423en_US
dc.identifier.spage11en_US
dc.identifier.epage18en_US
dc.identifier.isiWOS:000300964200002-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridChan, HL=7403402384en_US
dc.identifier.scopusauthoridMegow, N=8680826900en_US
dc.identifier.scopusauthoridSitters, R=54990816300en_US
dc.identifier.scopusauthoridVan Stee, R=6701387737en_US
dc.identifier.citeulike10205161-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats