Paper Info
Title
Make it practical: a generic linear-time algorithm for solving maximum-weightsum problems
Abstract
In this paper we propose a new method for deriving a practical linear-time algorithm from the specification of a maximum-weightsum problem: From the elements of a data structure x, find a subset which satisfies a certain property p and whose weightsum is maximum. Previously proposed methods for automatically generating linear-time algorithms are theoretically appealing, but the algorithms generated are hardly useful in practice due to a huge constant factor for space and time. The key points of our approach are to express the property p by a recursive boolean function over the structure x rather than a usual logical predicate and to apply program transformation techniques to reduce the constant factor. We present an optimization theorem, give a calculational strategy for applying the theorem, and demonstrate the effectiveness of our approach through several nontrivial examples which would be difficult to deal with when using the methods previously available.
Year
DOI
Venue
2000
10.1145/351240.351254
ICFP '00 Proceedings of the fifth ACM SIGPLAN international conference on Functional programming
Keywords
Field
DocType
satisfiability,boolean function,data structure,fusion
Boolean function,Data structure,Program transformation,Computer science,Spacetime,Algorithm,Theoretical computer science,Predicate (grammar),Program calculation,Time complexity,Recursion
Conference
Volume
Issue
ISSN
35
9
0362-1340
ISBN
Citations 
PageRank 
1-58113-202-6
22
1.41
References 
Authors
15
4
Name
Order
Citations
PageRank
Isao Sasano1516.18
Zhenjiang Hu2134199.25
Masato Takeichi359542.90
Mizuhito Ogawa413523.17