Treffer: Optimally competitive list batching
Title:
Optimally competitive list batching
Authors:
Source:
Algorithms theorye (Humlebaek, 8-10 July 2004)Lecture notes in computer science. :77-89
Publisher Information:
Berlin: Springer, 2004.
Publication Year:
2004
Physical Description:
print, 12 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Algorithme compétitif, Competitive algorithms, Algorithmique, Algorithmics, Algorítmica, Moyenne temporelle, Time average, Promedio temporal, Procédé discontinu, Batch process, Procedimiento discontínuo, Production par lot, Batch production, Producción por lote, Protocole TCP, Transmission control protocol, Protocolo TCP, Protocole transmission, Transmission protocol, Protocolo transmisión, Temps traitement, Processing time, Tiempo proceso
Document Type:
Konferenz
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
School of Computer Science, University of Nevada, Las Vegas, Nevada 89154, United States
School of Computer Science, The Interdisciplinary Center, Herzliya, Israel
Department of Computer Science, California State University Northridge, Northridge, CA 91330, United States
School of Computer Science, The Interdisciplinary Center, Herzliya, Israel
Department of Computer Science, California State University Northridge, Northridge, CA 91330, United States
ISSN:
0302-9743
Rights:
Copyright 2004 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.15993250
Database:
PASCAL Archive
Weitere Informationen
Batching has been studied extensively in the offline case, but many applications such as manufacturing or TCP acknowledgement require online solutions. We consider online batching problems, where the order of jobs to be batched is fixed and where we seek to minimize average flow time. We present optimally competitive algorithms for s-batch (competitive ratio 2) and p-batch problems (competitive ratio of 4). We also derive results for naturally occurring special cases. In particular, we consider the case of unit processing times.