Maximum Marking Problems with Accumulative Weight Functions
- 364 Downloads
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.
KeywordsProgram derivation Maximum marking problem Accumulative weight function Optimization problem
Unable to display preview. Download preview PDF.
- [BdM96]Bird, R., de Moor, O.: Algebra of Programming. Prentice Hall, Englewood Cliffs (1996)Google Scholar
- [Bir87]Bird, R.: An introduction to the theory of lists. In: Broy, M. (ed.) Logic of Programming and Calculi of Discrete Design. NATO ASI Series, vol. F36, pp. 5–42. Springer, Heidelberg (1987)Google Scholar
- [Bir98]Bird, R.: Introduction to Functional Programming using Haskell, 2nd edn. Prentice Hall, Englewood Cliffs (1998)Google Scholar
- [Gri90]Gries, D.: The maximum-segment-sum problem. In: Dijkstra, E.W. (ed.) Formal Development of Programs and Proofs, pp. 33–36. Addison-Wesley, Reading (1990)Google Scholar
- [PJH99]Jones, S.P., Hughes, J. (eds.): The Haskell 98 Report (February 1999), Available from http://www.haskell.org/definition/
- [SHTO00]Sasano, I., Hu, Z., Takeichi, M., Ogawa, M.: Make it practical: A generic linear-time algorithm for solving maximum-weightsum problems. In: Proceedings of the 5th ACM SIGPLAN International Conference on Functional Programming (ICFP 2000), Montreal, Canada, September 2000, pp. 137–149. ACM Press, New York (2000)CrossRefGoogle Scholar
- [SHTO01]Sasano, I., Hu, Z., Takeichi, M., Ogawa, M.: Solving a class of knapsack problems on recursive data structures (in Japanese). Computer Software 18(2), 59–63 (2001)Google Scholar
- [SHTO02]Sasano, I., Hu, Z., Takeichi, M., Ogawa, M.: Derivation of linear algorithm for mining optimized gain association rules. Computer Software 19(4), 39–44 (2002)Google Scholar