@inproceedings{53a36f59b05448b48d2327145657ad93,

title = "Maximum marking problems with accumulative weight functions",

abstract = "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.",

keywords = "Accumulative weight function, Maximum marking problem, Optimization problem, Program derivation",

author = "Isao Sasano and Mizuhito Ogawa and Zhenjiang Hu",

year = "2005",

doi = "10.1007/11560647_37",

language = "English",

isbn = "3540291075",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "562--578",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

note = "2nd International Colloquium on Theoretical Aspects of Computing - ICTAC 2005 ; Conference date: 17-10-2005 Through 21-10-2005",

}