Treffer: Maximum marking problems with accumulative weight functions
Title:
Maximum marking problems with accumulative weight functions
Authors:
Source:
Theoretical aspects of computing - ICTAC 2005 (Second international colloquium, Hanoi, Vietnam, October 17-21, 2005, proceedings)Lecture notes in computer science. :562-578
Publisher Information:
New York, NY: Springer, 2005.
Publication Year:
2005
Physical Description:
print, 15 ref 1
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, 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, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Fonction poids, Weight function, Función peso, Programmation mathématique, Mathematical programming, Programación matemática
Document Type:
Konferenz
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
RIEC, Tohoku University, 2-1-1 Katahira, Aoba-ku, Sendai 980-8577, Japan
School of Information Science, JAIST, 1-1 Asahidai, Nomi-shi, Ishikawa 923-1292, Japan
Department of Mathematical Informatics, School of Information Science and Technology, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
School of Information Science, JAIST, 1-1 Asahidai, Nomi-shi, Ishikawa 923-1292, Japan
Department of Mathematical Informatics, School of Information Science and Technology, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
ISSN:
0302-9743
Rights:
Copyright 2005 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.17265747
Database:
PASCAL Archive
Weitere Informationen
We present a new derivation of efficient algorithms for a class of optimization problems called maximum marking problems. We extend the class of weight functions used in the specification to allow for weight functions with accumulation, which is particularly useful when the weight of each element depends on adjacent elements. This extension of weight functions enables us to treat more interesting optimization problems such as a variant of the maximum segment sum problem and the fair bonus distribution problem. The complexity of the derived algorithm is linear with respect to the size of the input data.