@article{AdlerHS93, author = {Ilan Adler and Alan J. Hoffman and Ron Shamir}, title = {Monge and Feasibility Sequences in General Flow Problems}, journal = {Discrete Applied Mathematics}, volume = {44}, number = {1-3}, year = {1993}, pages = {21-38}, ee = {http://dx.doi.org/10.1016/0166-218X(93)90220-I}, bibsource = {DBLP, http://dblp.uni-trier.de} } @Article{AgSe96, author = "Pankaj K. Agarwal and Sandeep Sen", title = "Selection in Monotone Matrices and Computing $k$th Nearest Neighbors", journal = "Journal of Algorithms", volume = "20", number = "3", year = "1996", pages = "581-601", note = "A preliminary version appeared in \emph{Proceedings of the 4th Scandinavian Workshop on Algorithm Theory}, pages 13\---24, 1994." } @InProceedings{AgBa92+-conf, author = "Alok Aggarwal and Amotz Bar-Noy and Samir Khuller and Dina Kravets and Baruch Schieber", title = "Efficient Minimum Cost Matching Using Quadrangle Inequality", booktitle = "Proceedings of the 33rd Annual Symposium on Foundations of Computer Science", year = "1992", pages = "583-592" } @Article{AgBa95+, author = "Alok Aggarwal and Amotz Bar-Noy and Samir Khuller and Dina Kravets and Baruch Schieber", title = "Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality", journal = "Journal of Algorithms", volume = "19", number = "1", year = "1995", pages = "116-143", note = "A preliminary version appeared in \emph{Proceedings of the 33rd Annual Symposium on Foundations of Computer Science}, pages 583\---592, 1992." } @Article{AgKl90, author = "Alok Aggarwal and Maria Klawe", title = "Applications of Generalized Matrix Searching to Geometric Algorithms", journal = "Discrete Applied Mathematics", volume = "27", number = "1-2", year = "1990", pages = "3-23" } @InProceedings{AgKl86+-conf, author = "Alok Aggarwal and Maria M. Klawe and Shlomo Moran and Peter Shor and Robert Wilber", title = "Geometric Applications of a Matrix Searching Algorithm", booktitle = "Proceedings of the 2nd Annual Symposium on Computational Geometry", year = "1986", pages = "285-292" } @Article{AgKl87+, author = "Alok Aggarwal and Maria M. Klawe and Shlomo Moran and Peter W. Shor and Robert E. Wilber", title = "Geometric Applications of a Matrix-Searching Algorithm", journal = "Algorithmica", volume = "2", number = "1", year = "1987", pages = "195-208", note = "A preliminary version appeared in \emph{Proceedings of the 2nd Annual Symposium on Computational Geometry}, pages 285\---292, 1986." } @article{AgKr89, author = {Alok Aggarwal and Dina Kravets}, title = {A Linear Time Algorithm for Finding all Farthest Neighbors in a Convex Polygon}, journal = {Information Processing Letters}, volume = {31}, number = {1}, year = {1989}, pages = {17-20}, bibsource = {DBLP, http://dblp.uni-trier.de} } @InProceedings{AgKr90+-conf, author = "Alok Aggarwal and Dina Kravets and James K. Park and Sandeep Sen", title = "Parallel Searching in Generalized {M}onge Arrays with Applications", booktitle = "Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures", year = "1990", pages = "259-268" } @Article{AgKr97+, author = "Alok Aggarwal and Dina Kravets and James K. Park and Sandeep Sen", title = "Parallel Searching in Generalized {M}onge Arrays", journal = "Algorithmica", volume = "19", number = "3", year = "1997", pages = "291-317", note = "A preliminary version appeared in \emph{Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures}, pages 259\---268, 1990." } @InProceedings{AgPa88-conf, author = "Alok Aggarwal and James K. Park", title = "Notes on Searching in Multidimensional Monotone Arrays", booktitle = "Proceedings of the 29th Annual Symposium on Foundations of Computer Science", year = "1988", pages = "497-512" } @Article{AgPa93, author = "Alok Aggarwal and James K. Park", title = "Improved Algorithms for Economic Lot Size Problems", journal = "Operations Research", volume = "41", number = "3", year = "1993", pages = "549-571" } @InProceedings{AgSc93+-conf, author = "Alok Aggarwal and Baruch Schieber and Takeshi Tokuyama", title = "Finding a Minimum Weight $K$-Link Path in Graphs with {M}onge Property and Applications", booktitle = "Proceedings of the 9th Annual Symposium on Computational Geometry", year = "1993", pages = "189-197" } @Article{AgSc94+, author = "Alok Aggarwal and Baruch Schieber and Takeshi Tokuyama", title = "Finding a Minimum-Weight $k$-Link Path in Graphs with the Concave {M}onge Property and Applications", journal = "Discrete and Computational Geometry", volume = "12", year = "1994", pages = "263-280", note = "A preliminary version appeared in \emph{Proceedings of the 9th Annual Symposium on Computational Geometry}, pages 189\---197, 1993." } @InProceedings{AgTo93-conf, author = "Alok Aggarwal and Takeshi Tokuyama", title = "Consecutive Interval Query and Dynamic Programming on Intervals", booktitle = "Proceedings of the 4th International Symposium on Algorithms and Computation", series = "Lecture Notes in Computer Science", volume = "762", year = "1993", pages = "466-475" } %Conference version already in file @article{AgTo98, author = {Alok Aggarwal and Takeshi Tokuyama}, title = {Consecutive Interval Query and Dynamic Programming on Intervals}, journal = {Discrete Applied Mathematics}, volume = {85}, number = {1}, year = {1998}, pages = {1-24}, ee = {http://dx.doi.org/10.1016/S0166-218X(98)00021-3}, bibsource = {DBLP, http://dblp.uni-trier.de} } @Article{AlBr93, author = "Susanne Albers and Peter Brucker", title = "The Complexity of One-Machine Batching Problems", journal = "Discrete Applied Mathematics", volume = "47", number = "2", year = "1993", pages = "87-107" } @Article{ApAt90+, author = "Alberto Apostolico and Mikhail Atallah and Lawrence Larmore and Scott McFaddin", title = "Efficient Parallel Algorithms for String Editing and Related Problems", journal = "SIAM Journal on Computing", volume = "19", number = "5", year = "1990", pages = "968-988" } @Article{ArEg04, author = "Abdullah N. Arslan and Omer Egecioglu", title = "Dynamic Programming Based Approximation Algorithms for Sequence Alignment with Constraints", journal = "INFORMS Journal on Computing", volume = "16", number = "4", year = "2004", pages = "441-458" } @InProceedings{As91-conf, author = "Takao Asano", title = "Dynamic Programming on Intervals", booktitle = "Proceedings of the 2nd International Symposium on Algorithms", series = "Lecture Notes in Computer Science", volume = "557", year = "1991", pages = "199-207" } @Article{At92, author = "Mikhail J. Atallah", title = "Parallel Techniques for Computational Geometry", journal = "Proceedings of the IEEE", volume = "80", number = "9", year = "1992", pages = "1435-1448" } @Article{At93, author = "Mikhail J. Atallah", title = "A Faster Parallel Algorithm for a Matrix Searching Problem", journal = "Algorithmica", volume = "9", number = "2", year = "1993", pages = "156-167" } @Article{AtKo92, author = "Mikhail J. Atallah and S. Rao Kosaraju", title = "An Efficient Parallel Algorithm for the Row Minima of a Totally Monotone Matrix", journal = "Journal of Algorithms", volume = "13", number = "3", year = "1992", pages = "394-413", note = "A preliminary version appeared in \emph{Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms}, pages 394\---403, 1991." } @InProceedings{AtKo89+-conf, author = "Mikhail J. Atallah and S. Rao Kosaraju and Lawrence L. Larmore and Gary L. Miller and Shang-Hua Teng", title = "Constructing Trees in Parallel", booktitle = "Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures", year = "1989", pages = "421-431" } @Article{AuPa98+, author = "Vincenzo Auletta and Domenico Parente and Giuseppe Persiano", title = "Placing Resources on a Growing Line", journal = "Journal of Algorithms", volume = "26", number = "1", year = "1998", pages = "87-100" } @article{BaGi02, author = {Brenda S. Baker and Raffaele Giancarlo}, title = {Sparse Dynamic Programming for Longest Common Subsequence from Fragments}, journal = {J. Algorithms}, volume = {42}, number = {2}, year = {2002}, pages = {231-254}, ee = {http://dx.doi.org/10.1006/jagm.2002.1214}, bibsource = {DBLP, http://dblp.uni-trier.de} } @InProceedings{BaFe07+-conf, author = "Amotz Bar-Noy and Yi Feng and Mordecai J. Golin", title = "Paging Mobile Users Efficiently and Optimally", booktitle = "Proceedings of the 26th Annual IEEE Conference on Computer Communications", year = "2007" } @article{BaFe09, location = {http://www.scientificcommons.org/41004170}, title = {Computing rank convolutions with a mask}, author = {Laszlo Babai and Pedro Felzenszwalb}, journal={ACM Transactions on Algorithms (TALG)}, volume={6}, number={1}, pages={1--13}, issn={1549-6325}, year={2009}, publisher={ACM} } @InProceedings{BaGo06+-conf, author = "Amotz Bar-Noy and Mordecai J. Golin and Yan Zhang", title = "Online Dynamic Programming Speedups", booktitle = "Proceedings of the 4th Workshop on Approximation and Online Algorithms", series = "Lecture Notes in Computer Science", volume = "4368", year = "2006", pages = "43-54" } @article{BGY09, author = "Amotz Bar-Noy and Mordecai J. Golin and Yan Zhang", title = "Online Dynamic Programming Speedups", journal = "Theory of Computing Systems", volume = "45", number = "3", year = "2009", pages = "429-445" } @Article{BaLa04, author = "Amotz Bar-Noy and Richard E. Ladner", title = "Efficient Algorithms for Optimal Stream Merging for Media-on-Demand", journal = "SIAM Journal on Computing", volume = "33", number = "5", year = "2004", pages = "1011-1034" } @InProceedings{BeBr02+-conf, author = "Wolfgang W. Bein and Peter Brucker and Lawrence L. Larmore and James K. Park", title = "Fast Algorithms with Algebraic {M}onge Properties", booktitle = "Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science", series = "Lecture Notes in Computer Science", volume = "2420", year = "2002", pages = "104-117" } @Article{BeBr05+, author = "Wolfgang W. Bein and Peter Brucker and Lawrence L. Larmore and James K. Park", title = "The Algebraic {M}onge Property and Path Problems", journal = "Discrete Applied Mathematics", volume = "145", number = "3", year = "2005", pages = "455-464" } @Article{BeBr95+, author = "Wolfgang W. Bein and Peter Brucker and James K. Park and Pramod K. Pathak", title = "A {M}onge Property for the $d$-Dimensional Transportation Problem", journal = "Discrete Applied Mathematics", volume = "58", number = "2", year = "1995", pages = "97-109" } @Article{BePa96, author = "Wolfgang W. Bein and Pramod K. Pathak", title = "A Characterization of the {M}onge Property and Its Connection to Statistics", journal = "Demonstratio Mathematica", volume = "29", number = "2", year = "1996", pages = "451-457" } @Article{BeNe68, author = "M. Bellmore and G. L. Nemhauser", title = "The Traveling Salesman Problem: A Survey", journal = "Operations Research", volume = "16", number = "3", year = "1968", pages = "538-558" } @article{Blum2000, author = {Norbert Blum}, title = {Speeding Up Dynamic Programming without Omitting any Optimal Solution and Some Applications in Molecular Biology}, journal = {J. Algorithms}, volume = {35}, number = {2}, year = {2000}, pages = {129-168}, bibsource = {DBLP, http://dblp.uni-trier.de} } @Article{BoTe04, author = "Hans L. Bodlaender and Jan Arne Telle", title = "Space-Efficient Construction Variants of Dynamic Programming", journal = "Nordic Journal of Computing", volume = "11", number = "4", year = "2004", pages = "374-385" } @Article{BoGu94, author = "Al Borchers and Prosenjit Gupta", title = "Extending the Quadrangle Inequality to Speed-up Dynamic Programming", journal = "Information Processing Letters", volume = "49", number = "6", year = "1994", pages = "287-290" } @PhdThesis{Br94, author = "Phillip G. Bradford", title = "Parallel Dynamic Programming", school = "Indiana University", year = "1994" } @Article{BrFl97+, author = "Phillip G. Bradford and Rudolf Fleischer and Michiel Smid", title = "More Efficient Parallel Totally Monotone Matrix Searching", journal = "Journal of Algorithms", volume = "23", number = "2", year = "1997", pages = "386-400" } @article{BRS98, author = {Phillip G. Bradford and Gregory J. E. Rawlins and Gregory E. Shannon}, title = {Efficient Matrix Chain Ordering in Polylog Time}, publisher = {SIAM}, year = {1998}, journal = {SIAM Journal on Computing}, volume = {27}, number = {2}, pages = {466-490}, keywords = {parallel; dynamic programming; matrix chain ordering; optimization.}, url = {http://link.aip.org/link/?SMJ/27/466/1}, doi = {10.1137/S0097539794270698} } @Article{BrGo02+, author = "Phillip G. Bradford and Mordecai J. Golin and Lawrence L. Larmore and Wojciech Rytter", title = "Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the {M}onge Property", journal = "Journal of Algorithms", volume = "42", number = "2", year = "2002", pages = "277-303", note = "A preliminary version appeared in \emph{Proceedings of the 6th Annual European Symposium on Algorithms}, pages 43\---54, 1998." } @Article{BrRa98+, author = "Phillip G. Bradford and Gregory J. E. Rawlins and Gregory E. Shannon", title = "Efficient Matrix Chain Ordering in Polylog Time", journal = "SIAM Journal on Computing", volume = "27", number = "2", year = "1998", pages = "466-490", note = "A preliminary version appeared in \emph{Proceedings of the 8th International Parallel Processing Symposium}, pages 234\---241, 1994." } @Incollection{Bu05, author = "Rainer E. Burkard", title = "({G}eneralized) Convexity and Discrete Optimization", booktitle = "Generalized Convexity, Generalized Monotonicity and Applications", series = "Nonconvex Optimization and Its Applications", volume = "77", editor = "Andrew Eberhand and Nicolas Hadjisavvas and Dinh The Luc", publisher = "Springer Science+Business Media Inc.", address = "New York", year = "2005", chapter = "2", pages = "23-37" } @Article{BuCe98+, author = "Rainer E. Burkard and Eranda Cela and Gunter Rote and Gerhard J. Woeginger", title = "The Quadratic Assignment Problem with a Monotone Anti-{M}onge and a Symmetric {T}oeplitz Matrix: Easy and Hard Cases", journal = "Mathematical Programming", volume = "82", number = "1-2", year = "1998", pages = "125-158", note = "A preliminary version appeared in \emph{Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization}, pages 204\---218, 1996." } @Article{BuDe98, author = "Rainer E. Burkard and Vladimir G. Deineko", title = "On the Traveling Salesman Problem with a Relaxed {M}onge Matrix", journal = "Information Processing Letters", volume = "67", number = "5", year = "1998", pages = "231-237" } @Article{BuDe98+, author = "Rainer E. Burkard and Vladimir G. Deineko and Rene van Dal and Jack A. A. van der Veen and Gerhard J. Woeginger", title = "Well-Solvable Special Cases of the {TSP}: A Survey", journal = "SIAM Review", volume = "40", number = "3", year = "1998", pages = "496-546" } @Article{BuDe99+, author = "Rainer E. Burkard and Vladimir G. Deineko and Gerhard J. Woeginger", title = "The Travelling Salesman Problem on Permuted {M}onge Matrices", journal = "Journal of Combinatorial Optimization", volume = "2", number = "4", year = "1999", pages = "333-350" } @Article{BuKl96+, author = "Rainer E. Burkard and Bettina Klinz and Rudiger Rudolf", title = "Perspectives of {M}onge Properties in Optimization", journal = "Discrete Applied Mathematics", volume = "70", number = "2", year = "1996", pages = "95-161" } @Article{BuSa91, author = "Rainer E. Burkard and Wolfgang Sandholzer", title = "Efficiently Solvable Special Cases of Bottleneck Travelling Salesman Problems", journal = "Discrete Applied Mathematics", volume = "32", number = "1", year = "1991", pages = "61-76" } @Article{BuYi98, author = "Samuel R. Buss and Peter N. Yianilos", title = "Linear and ${O}(n \log n)$ Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours", journal = "SIAM Journal on Computing", volume = "27", number = "1", year = "1998", pages = "170-201", note = "A preliminary version appeared in \emph{Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms}, pages 65\---76, 1994." } @Article{ChHa94+, author = "Kun-Mao Chao and Ross C. Hardison and Webb Miller", title = "Recent Developments in Linear-Space Alignment Methods: A Survey", journal = "Journal of Computational Biology", volume = "1", number = "4", year = "1994", pages = "271-292" } @Article{ChDa03+, author = "Danny Z. Chen and Ovidiu Daescu and Xiaobo Sharon Hu and Jinhui Xu", title = "Finding an Optimal Path without Growing the Tree", journal = "Journal of Algorithms", volume = "49", number = "1", year = "2003", pages = "13-41", note = "A preliminary version appeared in \emph{Proceedings of the 6th Annual European Symposium on Algorithms}, pages 356\---367, 1998." } @Article{Ch96, author = "Victor Chepoi", title = "On Distances in Benzenoid Systems", journal = "Journal of Chemical Information and Computer Sciences", volume = "36", number = "6", year = "1996", pages = "1169-1172" } @InProceedings{CrLa02+-conf, author = "Maxime Crochemore and Gad M. Landau and Michal Ziv-Ukelson", title = "A Sub-quadratic Sequence Alignment Algorithm for Unrestricted Cost Matrices", booktitle = "Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms", year = "2002", pages = "679-688" } %Dean04 @article{Dean04, title = {Algorithms for minimum-cost paths in time-dependent networks with waiting policies}, author = {Brian C. Dean}, journal = {Networks}, volume = {44}, number = {1}, year = {2004}, issn = {0028-3045}, pages = {41--46}, doi = {http://dx.doi.org/10.1002/net.v44:1}, publisher = {Wiley-Interscience}, address = {New York, NY, USA}, } @Unpublished{De-Submit, author = "Brian C. Dean", title = "Speeding up Stochastic Dynamic Programming with Zero-Delay Convolution", note = "Submitted to Journal of Optimization Theory and Applications", year = "2006" } @InProceedings{Dekl06+-conf, author = "Vladimir G. Deineko and Bettina Klinz and Gerhard J. Woeginger", title = "Four Point Conditions and Exponential Neighborhoods for Symmetric {TSP}", booktitle = "Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms", year = "2006", pages = "544-553" } @Article{DeSt05+, author = "Vladimir G. Deineko and George Steiner and Zhihui Xue", title = "Robotic-Cell Scheduling: Special Polynomially Solvable Cases of the Traveling Salesman Problem on Permuted {M}onge Matrices", journal = "Journal of Combinatorial Optimization", volume = "9", number = "4", year = "2005", pages = "381-399" } @InProceedings{DeTi06-conf, author = "Vladimir G. Deineko and Alexander Tiskin", title = "One-Sided {M}onge {TSP} Is {NP}-Hard", booktitle = "Proceedings of the International Conference on Computational Science and Its Applications", series = "Lecture Notes in Computer Science", volume = "3982", year = "2006", pages = "793-801" } @article{Denado67, author = {Eric V. Denardo }, title = {Contraction Mappings in the Theory Underlying Dynamic Programming}, journal = {SIAM Review}, volume = {9}, number = {2}, month = {April}, year = {1967}, pages = {165-177}, } @Article{De04, author = "Vitali M. Demidenko", title = "Conic Characterization of {M}onge Matrices", journal = "Cybernetics and Systems Analysis", volume = "40", number = "4", year = "2004", pages = "537-546" } @article{DuRu98, author = {T. Dud\'{a}s and R. Rudolf}, title = {Spanning trees and shortest paths in Monge graphs}, journal = {Computing}, volume = {60}, number = {2}, year = {1998}, issn = {0010-485X}, pages = {109--119}, doi = {http://dx.doi.org/10.1007/BF02684360}, publisher = {Springer-Verlag New York, Inc.}, address = {New York, NY, USA}, } @article{Dumit06, author = {Sorina Dumitrescu}, title = {Faster algorithm for designing optimal prefix-free codes with unequal letter costs}, journal = {Fundamenta Informaticae}, volume = {73}, number = {1-2}, year = {2006}, pages = {107-117} } @Article{DuWu04, author = "Sorina Dumitrescu and Xiaolin Wu", title = "Algorithms for Optimal Multi-Resolution Quantization", journal = "Journal of Algorithms", volume = "50", number = "1", year = "2004", pages = "1-22" } @Article{DuWu04+, author = "Sorina Dumitrescu and Xiaolin Wu and Zhe Wang", title = "Globally Optimal Uneven Error-Protected Packetization of Scalable Code Streams", journal = "IEEE Transactions on Multimedia", volume = "6", number = "2", year = "2004", pages = "230-239" } @PhdThesis{Ep89, author = "David Eppstein", title = "Efficient Algorithms for Sequence Analysis with Concave and Convex Gap Costs", school = "Columbia University", year = "1989" } @Article{Ep90, author = "David Eppstein", title = "Sequence Comparison with Mixed Convex and Concave Costs", journal = "Journal of Algorithms", volume = "11", number = "1", year = "1990", pages = "85-101" } @InProceedings{EpGa88+-conf, author = "David Eppstein and Zvi Galil and Raffaele Giancarlo", title = "Speeding up Dynamic Programming", booktitle = "Proceedings of the 29th Annual Symposium on Foundations of Computer Science", year = "1988", pages = "488-496" } @InProceedings{EpGa90+-conf, author = "David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe F. Italiano", title = "Sparse Dynamic Programming", booktitle = "Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms", year = "1990", pages = "513-522" } @Article{EpGa92a+, author = "David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe F. Italiano", title = "Sparse Dynamic Programming {I}: Linear Cost Functions", journal = "Journal of the ACM", volume = "39", number = "3", year = "1992", pages = "519-545", note = "A preliminary version appeared in \emph{Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms}, pages 513\---522, 1990." } @Article{EpGa92b+, author = "David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe F. Italiano", title = "Sparse Dynamic Programming {II}: Convex and Concave Cost Functions", journal = "Journal of the ACM", volume = "39", number = "3", year = "1992", pages = "546-567", note = "A preliminary version appeared in \emph{Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms}, pages 513\---522, 1990." } @article{FeTz91, author = {Awi Federgruen and Michal Tzur}, title = {A simple forward algorithm to solve general dynamic lot sizing models with $n$ periods in $O(n log n)$ or $O(n)$ time}, journal = {Management Science}, volume = {37}, number = {8}, year = {1991}, pages = {909--925}, doi = {http://dx.doi.org/10.1287/mnsc.37.8.909}, publisher = {INFORMS} } @article{FeTz95, author = {Awi Federgruen and Michal Tzur}, title = {Fast solution and detection of minimal forecast horizons in dynamic programs with a single indicator of the future: applications to dynamic lot-sizing models}, journal = {Management Science}, volume = {41}, number = {5}, year = {1995}, pages = {874--893}, doi = {http://dx.doi.org/10.1287/mnsc.41.5.874}, publisher = {INFORMS} } @techreport{FeHu04, edition = {TR2004-1963}, institution = {Cornell Computing and Information Science, TR2004-1963}, keywords = {belief\_propagation, chamfer\_distance, object\_detection}, author = {P.F. Felzenszwalb and D.P. Huttenlocher}, month = {September}, title = {Distance Transforms of Sampled Functions}, url = {http://citeseer.ist.psu.edu/696385.html}, year = {2004} } @Article{FlGo06+, author = "Rudolf Fleischer and Mordecai J. Golin and Yan Zhang", title = "Online Maintenance of $k$-Medians and $k$-Covers on a Line", journal = "Algorithmica", volume = "45", number = "4", year = "2006", pages = "549-567", note = "A preliminary version appeared in \emph{Proceedings of the 9th Scandinavian Workshop on Algorithm Theory}, pages 102\---113, 2004." } @MastersThesis{Ga03a, author = "Travis Gagie", title = "Dynamic Length-Restricted Coding", school = "University of Toronto", year = "2003" } @InProceedings{Ga03b, author = "Travis Gagie", title = "New Ways to Construct Binary Search Trees", booktitle = "Proceedings of the 14th Annual International Symposium on Algorithms and Computation", series = "Lecture Notes in Computer Science", volume = "2906", year = "2003", pages = "537-643" } @Article{GaGi89, author = "Zvi Galil and Raffaele Giancarlo", title = "Speeding up Dynamic Programming with Applications to Molecular Biology", journal = "Theoretical Computer Science", volume = "64", number = "1", year = "1989", pages = "107-118" } @Article{GaPa90, author = "Zvi Galil and Kunsoo Park", title = "A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming", journal = "Information Processing Letters", volume = "33", number = "6", year = "1990", pages = "309-311" } @Article{GaPa92, author = "Zvi Galil and Kunsoo Park", title = "Dynamic Programming with Convexity, Concavity and Sparsity", journal = "Theoretical Computer Science", volume = "92", number = "1", year = "1992", pages = "49-76" } @Article{GaPa94, author = "Zvi Galil and Kunsoo Park", title = "Parallel Algorithms for Dynamic Programming Recurrences with More than ${O}(1)$ Dependency", journal = "Journal of Parallel and Distributed Computing", volume = "21", number = "2", year = "1994", pages = "213-222" } @Article{Ga74, author = "M. R. Garey", title = "Optimal Binary Search Trees with Restricted Maximal Depth", journal = "SIAM Journal on Computing", volume = "3", number = "2", year = "1974", pages = "101-110" } @Article{GaJo98+, author = "Alfredo Garcia and Pedro Jodra and Javier Tejel", title = "An Efficient Algorithm for On-Line Searching of Minima in {M}onge Path-Decomposable Tridimensional Arrays", journal = "Information Processing Letters", volume = "68", number = "1", year = "1998", pages = "3-9" } @Article{Ga95, author = "William G. Gardner", title = "Efficient Convolution without Input-Output Delay", journal = "Journal of the Audio Engineering Society", volume = "42", number = "3", year = "1995", pages = "127-136" } @Article{GaPl06, author = "Martin Gavalec and Jan Plavka", title = "Computing an Eigenvector of a {M}onge Matrix in Max-Plus Algebra", journal = "Mathematical Methods of Operations Research", volume = "63", number = "3", year = "2006", pages = "543-551" } @Article{Gi71, author = "Edgar N. Gilbert", title = "Codes Based on Inaccurate Source Probabilities", journal = "IEEE Transactions on Information Theory", volume = "17", number = "3", year = "1971", pages = "304-314" } @Article{GiMo59, author = "Edgar N. Gilbert and Edward F. Moore", title = "Variable Length Encodings", journal = "Bell System Technical Journal", volume = "38", year = "1959", pages = "933-967" } @Article{Go81, author = "L. Gotlieb", title = "Optimal Multi-Way Search Trees", journal = "SIAM Journal on Computing", volume = "10", number = "3", year = "1981", pages = "422-433" } @Article{GoWo81, author = "L. Gotlieb and Derick Wood", title = "The Construction of Optimal Multiway Search Trees and the Monotonicity Principle", journal = "International Journal of Computer Mathematics, Section A: Programming Theory and Methods", volume = "9", number = "1", year = "1981", pages = "17-24" } @TechReport{Gu05, author = "Oktay Gunluk", title = "A Pricing Problem under {M}onge Property", type = "IBM Research Report", number = "RC23823", institution = "IBM Research Division, Thomas J.~Watson Research Center", year = "2005" } @Book{Gu97, author = "Dan Gusfield", title = "Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology", publisher = "Cambridge University Press", year = "1997", } @inproceedings{Halmanetal08, author = {Halman, Nir and Klabjan, Diego and Li, Chung-Lun and Orlin, James and Simchi-Levi, David}, title = {Fully polynomial time approximation schemes for stochastic dynamic programs}, booktitle = {Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms}, series = {SODA '08}, year = {2008}, location = {San Francisco, California}, pages = {700--709}, numpages = {10}, url = {http://portal.acm.org.lib.ezproxy.ust.hk/citation.cfm?id=1347082.1347159}, acmid = {1347159}, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA, USA}, } @Article{HaTa91, author = "Refael Hassin and Arie Tamir", title = "Improved Complexity Bounds for Location Problems on the Real Line", journal = "Operations Research Letters", volume = "10", number = "7", year = "1991", pages = "395-402" } @InProceedings{HeCh97-conf, author = "Xin He and Zhi-Zhong Chen", title = "Shortest Path in Complete Bipartite Digraph Problem and its Applications", booktitle = "Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms", year = "1997", pages = "230-238" } @Article{HeCh99, author = "Xin He and Zhi-Zhong Chen", title = "An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications", journal = "SIAM Journal on Computing", volume = "29", number = "1", year = "1999", pages = "65-80", note = "A preliminary version appeared in \emph{Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms}, pages 230\---238, 1997." } @article{HLLW09, title={{A unified algorithm for accelerating edit-distance computation via text-compression}}, author={Danny Hermelin and Gad M. Landau and Shir Landa and Oren Weimann}, journal={Proceedings of the 26th STACS}, pages={529--540}, year={2009} } @Article{Hi75, author = "Daniel S. Hirschberg", title = "A Linear Space Algorithm for Computing Maximal Common Subsequences", journal = "Communications of the ACM", volume = "18", number = "6", year = "1975", pages = "341-343" } @Article{HiLa87a, author = "Daniel S. Hirschberg and Lawrence L. Larmore", title = "The Least Weight Subsequence Problem", journal = "SIAM Journal on Computing", volume = "16", number = "4", year = "1987", pages = "628-638" } @Article{HiLa87b, author = "Daniel S. Hirschberg and Lawrence L. Larmore", title = "New Applications of Failure Functions", journal = "Journal of the ACM", volume = "34", number = "3", year = "1987", pages = "616-625" } @article{HoTaWu08, author = {Pei-Hao Ho and Arie Tamir and Bang Ye Wu}, title = {{Minimum ${L}_{\mbox{k}}$ path partitioning - An illustration of the {M}onge property}}, journal = {Oper. Res. Lett.}, volume = {36}, number = {1}, year = {2008}, pages = {43-45}, ee = {http://dx.doi.org/10.1016/j.orl.2007.03.010}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{HoWaMo94, author = {Stan van Hoese and Albert Wagelman and Bram Moerman }, title = {Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions}, journal = {European Journal of Operational Research}, volume = {75}, year = {1994}, pages = {312-331} } @TechReport{HoPr05, author = "Xiaoling Hou and Andras Prekopa", title = "{M}onge Property and Bounding Multivariate Probability Distribution Functions with Given Marginals and Covariances", type = "RUTCOR Research Report", number = "27-2005", institution = "Rutgers Center for Operations Research, Rutgers University, New Jersey", year = "2005" } @InProceedings{HuLa05+-conf, author = "T. C. Hu and Lawrence L. Larmore and J. David Morgenthaler", title = "Optimal Integer Alphabetic Trees in Linear Time", booktitle = "Proceedings of the 13th Annual European Symposium on Algorithms", series = "Lecture Notes in Computer Science", volume = "3669", year = "2005", pages = "226-237" } @ARTICLE{HuMo94, author = {Hu, T.C and Morgenthaler, J.D.}, title = {{Dynamic Programming and Graph Optimization Problems}}, journal = {Computers and Mathematics with Applications}, year = {1994}, volume = {27}, pages = {53--53}, publisher = {PERGAMON PRESS} } @Article{HuSh82, author = "T. C. Hu and M. T. Shing", title = "Computation of Matrix Chain Products. Part I", journal = "SIAM Journal on Computing", volume = "11", number = "2", year = "1982", pages = "362-373" } @Article{HuSh84, author = "T. C. Hu and M. T. Shing", title = "Computation of Matrix Chain Products. Part II", journal = "SIAM Journal on Computing", volume = "13", number = "2", year = "1984", pages = "228-251" } @Article{HuTa72, author = "T. C. Hu and K. C. Tan", title = "Path Length of Binary Search Trees", journal = "SIAM Journal on Applied Mathematics", volume = "22", number = "2", year = "1972", pages = "225-234" } @Article{HuTu71, author = "T. C. Hu and A. C. Tucker", title = "Optimal Computer Search Trees and Variable-Length Alphabetical Codes", journal = "SIAM Journal on Applied Mathematics", volume = "21", number = "4", year = "1971", pages = "514-532" } @InProceedings{Hu52, author = "David A. Huffman", title = "A Method for the Construction of Minimum-Redundancy Codes", booktitle = "Proceedings of the Institution of Radio Engineers", volume = "40", year = "1952", pages = "1098-1101" } @inproceedings{HLW08, author = {Guan-Shieng Huang and Jia Jie Liu and Yue-Li Wang}, title = {Sequence Alignment Algorithms for Run-Length-Encoded Strings}, booktitle = {Proceedings of 14th Annual International Computing and Combinatorics Conference (COCOON'08)}, year = {2008}, pages = {319-330}, ee = {http://dx.doi.org/10.1007/978-3-540-69733-6_32} } @article{HuSz77, author = {James W. Hunt and Thomas G. Szymanski}, title = {A fast algorithm for computing longest common subsequences}, journal = {Commun. ACM}, volume = {20}, number = {5}, year = {1977}, issn = {0001-0782}, pages = {350--353}, doi = {http://doi.acm.org/10.1145/359581.359603}, publisher = {ACM}, address = {New York, NY, USA} } @Article{It76, author = "Alon Itai", title = "Optimal Alphabetic Trees", journal = "SIAM Journal on Computing", volume = "5", number = "1", year = "1976", pages = "9-18" } @Article{Ka61, author = "Richard M. Karp", title = "Minimum-Redundancy Coding for the Discrete Noiseless Channel", journal = "IEEE Transactions on Information Theory", volume = "7", number = "1", year = "1961", pages = "27-38" } @article{KLR97, author = {Marek Karpinski and Lawrence L. Larmore and Wojciech Rytter}, title = {Correctness of Constructing Optimal Alphabetic Trees Revisited}, journal = {Theoretical Computer Science}, volume = {180}, number = {1-2}, year = {1997}, pages = {309-324}, ee = {http://dx.doi.org/10.1016/S0304-3975(96)00296-4}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{KsPP2010, author = {Khajeh-Saeed,Ali and Poole, Stephen and Blair Perot, J.}, title = {Acceleration of the Smith-Waterman algorithm using single and multiple graphics processors}, journal = {J. Comput. Phys.}, volume = {229}, issue = {11}, month = {June}, year = {2010}, issn = {0021-9991}, pages = {4247--4258}, numpages = {12}, url = {http://dx.doi.org/10.1016/j.jcp.2010.02.009}, doi = {http://dx.doi.org/10.1016/j.jcp.2010.02.009}, acmid = {1752849}, publisher = {Academic Press Professional, Inc.}, address = {San Diego, CA, USA}, keywords = {GPU, Graphics processor, Parallel scan, Sequence matching, Smith-Waterman}, } @InProceedings{KiTh01-conf, author = "Valerie King and Mikkel Thorup", title = "A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms", booktitle = "Proceedings of the 7th International Conference on Computing and Combinatorics", series = "Lecture Notes in Computer Science", volume = "2108", year = "2001", pages = "268-277" } @Article{Ki88, author = "Jeffrey H. Kingston", title = "A New Proof of the {G}arsia-{W}achs Algorithm", journal = "Journal of Algorithms", volume = "9", number = "1", year = "1988", pages = "129-136" } @TechReport{Kl89, author = "Maria M. Klawe", title = "A Simple Linear Time Algorithm for Concave One-Dimensional Dynamic Programming", type = "Technical Report", number = "89-16", institution = "Department of Computer Science, University of British Columbia", year = "1989" } @InProceedings{Kl90-conf, author = "Maria M. Klawe", title = "Superlinear Bounds on Matrix Searching", booktitle = "Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms", year = "1990", pages = "485-493" } @Article{Kl92, author = "Maria M. Klawe", title = "Superlinear Bounds for Matrix Searching Problems", journal = "Journal of Algorithms", volume = "13", number = "1", year = "1992", pages = "55-78", note = "A preliminary version appeared in \emph{Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms}, pages 485\---493, 1990." } @Article{KlKl90, author = "Maria M. Klawe and Daniel J. Kleitman", title = "An Almost Linear Time Algorithm for Generalized Matrix Searching", journal = "SIAM Journal on Discrete Mathematics", volume = "3", number = "1", year = "1990", pages = "81-97" } @Article{KlMu95, author = "Maria M. Klawe and Brendan Mumey", title = "Upper and Lower Bounds on Constructing Alphabetic Binary Trees", journal = "SIAM Journal on Discrete Mathematics", volume = "8", number = "4", year = "1995", pages = "638-651", note = "A preliminary version appeared in \emph{Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms}, pages 185\---193, 1993." } @Article{KlRu95+, author = "Bettina Klinz and Rudiger Rudolf and Gerhard J. Woeginger", title = "Permuting Matrices to Avoid Forbidden Submatrices", journal = "Discrete Applied Mathematics", volume = "60", number = "1-3", year = "1995", pages = "223-248" } @article{KMW10, title={{Shortest paths in directed planar graphs with negative lengths: A linear-space $O (n log 2 n)$-time algorithm}}, author={Philip N. Klein and Shay Mozes and Oren and Weimann}, journal={ACM Transactions on Algorithms (TALG)}, volume={6}, number={2}, pages={1--18}, issn={1549-6325}, year={2010}, publisher={ACM} } @Article{Kn71, author = "Donald E. Knuth", title = "Optimum Binary Search Trees", journal = "Acta Informatica", volume = "1", year = "1971", pages = "14-25" } @Article{KnPl81, author = "Donald E. Knuth and Michael F. Plass", title = "Breaking Paragraphs into Lines", journal = "Software: Practice and Experience", volume = "11", number = "11", year = "1981", pages = "1119-1184" } @InProceedings{KrPa90-conf, author = "Dina Kravets and James K. Park", title = "Selection and Sorting in Totally Monotone Arrays", booktitle = "Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms", year = "1990", pages = "494-502" } @Article{KrPa91, author = "Dina Kravets and James K. Park", title = "Selection and Sorting in Totally Monotone Arrays", journal = "Theory of Computing Systems (formerly Mathematical Systems Theory)", volume = "24", number = "3", year = "1991", pages = "201-220", note = "A preliminary version appeared in \emph{Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms}, pages 494\---502, 1990." } @Article{KrGa04+, author = "Bhaskar Krishnamachari and Rung-Hung Gau and Stephen B. Wicker and Zygmunt J. Haas", title = "Optimal Sequential Paging in Cellular Wireless Networks", journal = "Wireless Networks", volume = "10", number = "2", year = "2004", pages = "121-131" } @InProceedings{LaMi99+, author = "Eduardo Sany Laber and Ruy Luiz Milidiu and Artur Alves Pessoa", title = "Practical Constructions of {L}-Restricted Alphabetic Prefix Codes", booktitle = "Proceedings of the String Processing and Information Retrieval Symposium and International Workshop on Groupware", year = "1999", pages = "115-119" } @Article{LaCh93, author = "Tak Wah Lam and Kwong-Fai Chan", title = "Finding Least-Weight Subsequences with Fewer Processors", journal = "Algorithmica", volume = "9", number = "6", year = "1993", pages = "615-628", note = "A preliminary version appeared in \emph{Proceedings of the SIGAL International Symposium on Algorithms}, pages 318\---327, 1990." } @Article{LaZi01, author = "Gad M. Landau and Michal Ziv-Ukelson", title = "On the Common Substring Alignment Problem", journal = "Journal of Algorithms", volume = "41", number = "2", year = "2001", pages = "338-359" } @Article{La87, author = "Lawrence L. Larmore", title = "Height Restricted Optimal Binary Trees", journal = "SIAM Journal on Computing", volume = "16", number = "6", year = "1987", pages = "1115-1123" } @InProceedings{LaHi90-conf, author = "Lawrence L. Larmore and Daniel S. Hirschberg", title = "Length-Limited Coding", booktitle = "Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms", year = "1990", pages = "310-318" } @Article{LaHi90, author = "Lawrence L. Larmore and Daniel S. Hirschberg", title = "A Fast Algorithm for Optimal Length-Limited {H}uffman Codes", journal = "Journal of the ACM", volume = "37", number = "3", year = "1990", pages = "464-473", note = "A preliminary version appeared in \emph{Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms}, pages 310\---318, 1990." } @InProceedings{LaPr91-conf, author = "Lawrence L. Larmore and Teresa M. Przytycka", title = "Parallel Construction of Trees with Optimal Weighted Path Length", booktitle = "Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures", year = "1991", pages = "71-80" } @Article{LaPr94, author = "Lawrence L. Larmore and Teresa M. Przytycka", title = "A Fast Algorithm for Optimum Height-Limited Alphabetic Binary Trees", journal = "SIAM Journal on Computing", volume = "23", number = "6", year = "1994", pages = "1283-1312" } @InProceedings{LaSc90-conf, author = "Lawrence L. Larmore and Baruch Schieber", title = "On-line Dynamic Programming with Applications to the Prediction of {R}{N}{A} Secondary Structure", booktitle = "Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms", year = "1990", pages = "503-512" } @Article{LaSc91, author = "Lawrence L. Larmore and Baruch Schieber", title = "On-line Dynamic Programming with Applications to the Prediction of {R}{N}{A} Secondary Structure", journal = "Journal of Algorithms", volume = "12", number = "3", year = "1991", pages = "490-515", note = "A preliminary version appeared in \emph{Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms}, pages 503\---512, 1990." } @InProceedings{LiMo02, author = "Mike Liddell and Alistair Moffat", title = "Incremental Calculation of Minimum-Redundancy Length-Restricted Codes (Extended Abstract)", booktitle = "Proceedings of the Data Compression Conference", year = "2002", pages = "182-191" } @InProceedings{LiMo01a, author = "Mike Liddell and Alistair Moffat", title = "Length-Restricted Coding in Static and Dynamic Frameworks (Extended Abstract)", booktitle = "Proceedings of the Data Compression Conference", year = "2001", pages = "133-142" } @InProceedings{LiMo01b, author = "Mike Liddell and Alistair Moffat", title = "Length-Restricted Coding Using Modified Probability Distributions", booktitle = "Proceedings of the 24th Australasian Conference on Computer Science", year = "2001", pages = "117-124" } @Article{LuHu05, author = "Chin Lung Lu and Yen Pin Huang", title = "A Memory-Efficient Algorithm for Multiple Sequence Alignment with Constraints", journal = "Bioinformatics", volume = "21", number = "1", year = "2005", pages = "20-30" } @article{Lucet09, author = {Lucet, Yves}, title = {New sequential exact Euclidean distance transform algorithms based on convex analysis}, journal = {Image and Vision Computing}, volume = {27}, number = {1-2}, year = {2009}, issn = {0262-8856}, pages = {37--44}, doi = {http://dx.doi.org/10.1016/j.imavis.2006.10.011}, publisher = {Butterworth-Heinemann}, address = {Newton, MA, USA}, } @Article{Ma98, author = "Ion I. Mandoiu", title = "Optimum Extensions of Prefix Codes", journal = "Information Processing Letters", volume = "66", number = "1", year = "1998", pages = "35-40" } @InProceedings{MaPa91+-conf, author = "Yishay Mansour and James K. Park and Baruch Schieber and Sandeep Sen", title = "Improved Selection on Totally Monotone Arrays", booktitle = "Proceedings of the 11th Conference on Foundations of Software Technology and Theoretical Computer Science", series = "Lecture Notes in Computer Science", volume = "560", year = "1991", pages = "347-359" } @Article{MaPa93+, author = "Yishay Mansour and James K. Park and Baruch Schieber and Sandeep Sen", title = "Improved Selection in Totally Monotone Arrays", journal = "International Journal on Computational Geometry \& Applications", volume = "3", number = "2", year = "1993", pages = "115-132", note = "A preliminary version appeared in \emph{Proceedings of the 11th Conference on Foundations of Software Technology and Theoretical Computer Science}, pages 347\---359, 1991." } @article{MaPA80, author = {William J. Masek and Mike Paterson}, title = {A Faster Algorithm Computing String Edit Distances}, journal = {J. Comput. Syst. Sci.}, volume = {20}, number = {1}, year = {1980}, pages = {18-31}, bibsource = {DBLP, http://dblp.uni-trier.de} } @Article{Me83, author = "Nimrod Megiddo", title = "Applying Parallel Computation Algorithms in the Design of Serial Algorithms", journal = "Journal of the ACM", volume = "30", number = "4", year = "1983", pages = "852-865" } @Article{MiLa01, author = "R. L. Milidiu and E. S. Laber", title = "Bounding the Inefficiency of Length-Restricted Prefix Codes", journal = "Algorithmica", volume = "31", number = "4", year = "2001", pages = "513-529" } @InProceedings{MiLa00a, author = "Ruy Luiz Milidiu and Eduardo Sany Laber", title = "Linear Time Recognition of Optimal {L}-Restricted Prefix Codes (Extended Abstract)", booktitle = "Proceedings of the 4th Latin American Symposium on Theoretical Informatics", series = "Lecture Notes in Computer Science", volume = "1776", year = "2000", pages = "227-236" } @Article{MiLa00b, author = "Ruy Luiz Milidiu and Eduardo Sany Laber", title = "The {WARM-UP} Algorithm: A {L}agrangian Construction of Length Restricted {H}uffman Codes", journal = "SIAM Journal on Computing", volume = "30", number = "5", year = "2000", pages = "1405-1426" } @InProceedings{MiPe99+, author = "Ruy Luiz Milidiu and Artur Alves Pessoa and Eduardo Sany Laber", title = "Efficient Implementation of the {WARM-UP} Algorithm for the Construction of Length-Restricted Prefix Codes", booktitle = "Selected Papers of the International Workshop on Algorithm Engineering and Experimentation", series = "Lecture Notes in Computer Science", volume = "1619", year = "1999", pages = "1-17" } @InProceedings{MiPe98+, author = "Ruy Luiz Milidiu and Artur Alves Pessoa and Eduardo Sany Laber", title = "In-Place Length-Restricted Prefix Coding", booktitle = "Proceedings of String Processing and Information Retrieval: A South American Symposium", year = "1998", pages = "50-59" } @Article{MiMy88, author = {W. Miller and E. W. Myers}, title = {Sequence comparison with concave weighting functions}, journal = {Bulletin of Mathematical Biology}, volume = {50}, number = {2}, pages = {97--120}, year = {1988}, keywords = {MolBio, similarity, homology, alignment, LCS, LCSS, DNA, concave, linear, affine, string strings sequence, BMB, gap weight, block insert, dynamic programming algorithm DPA}, abstract = {O(m*n) if w(k)=w(k+a)+b solvable for k given a, b in O(1) O(m*n*(log n + log m)) otherwise also includes Hirschberg linear space technique}, } @Article{MuRa82, author = "J. Ian Munro and Raul J. Ramirez", title = "Reducing Space Requirements for Shortest Path Problems", journal = "Operations Research", volume = "30", number = "5", year = "1982", pages = "1009-1013" } @Article{MyMi88, author = "Eugene W. Myers and Webb Miller", title = "Optimal Alignments in Linear Space", journal = "Bioinformatics (formerly Computer Applications in the Biosciences)", volume = "4", number = "1", year = "1988", pages = "11-17" } @Article{NaOl98, author = "Koji Nakano and Stephan Olariu", title = "An Efficient Algorithm for Row Minima Computations on Basic Reconfigurable Meshes", journal = "IEEE Transactions on Parallel and Distributed Systems", volume = "9", number = "6", year = "1998", pages = "561-569" } @PhdThesis{Pa91, author = "James K. Park", title = "The {M}onge Array: An Abstraction and Its Applications", school = "Massachusetts Institute of Technology", year = "1991" } @article{Park91_TSP, author = {James K. Park}, title = {A Special Case of the n-Vertex Traveling-Salesman Problem that can be Solved in O(n) Time}, journal = {Information Processing Letters}, volume = {40}, number = {5}, year = {1991}, pages = {247-254}, bibsource = {DBLP, http://dblp.uni-trier.de} } @Article{PaRa99, author = "D. Stott Parker and Prasad Ram", title = "The Construction of {H}uffman Codes is a Submodular (``Convex'') Optimization Problem over a Lattice of Binary Trees", journal = "SIAM Journal on Computing", volume = "28", number = "5", year = "1999", pages = "1875-1905" } @article{PRW94, author = " Ulrich Pferschy and R{\"u}diger Rudolf and Gerhard J. Woeginger", title = "Monge Matrices Make Maximization Manageable", journal = {Operations Research Letters}, volume = {16}, year = {1994}, pages = {245-254}, url = "citeseer.ist.psu.edu/pferschy93monge.html" } @Article{PaRo03+, author = "Michal Parnas and Dana Ron and Ronitt Rubinfeld", title = "On Testing Convexity and Submodularity", journal = "SIAM Journal on Computing", volume = "32", number = "5", year = "2003", pages = "1158-1184", note = "A preliminary version appeared in \emph{Proceedings of the 6th International Workshop on Randomization and Approximation Techniques}, pages 11\---25, 2002." } @Article{QuSp98+, author = "Maurice Queyranne and Frits C. R. Spieksma and Fabio Tardella", title = "A General Class of Greedily Solvable Linear Programs", journal = "Mathematics of Operations Research", volume = "23", number = "4", year = "1998", pages = "892-908", note = "A preliminary version appeared in \emph{Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference}, pages 385\---399, 1993." } @Article{RaGa92, author = "Yuval Rabani and Zvi Galil", title = "On the Space Complexity of Some Algorithms for Sequence Comparison", journal = "Theoretical Computer Science", volume = "95", number = "2", year = "1992", pages = "231-244" } @Article{RaSa92+, author = "Sailesh K. Rao and P. Sadayappan and Frank K. Hwang and Peter W. Shor", title = "The Rectilinear {S}teiner Arborescence Problem", journal = "Algorithmica", volume = "7", number = "2-3", year = "1992", pages = "277-288" } @Article{RuWo95, author = "Rudiger Rudolf and Gerhard J. Woeginger", title = "The Cone of {M}onge Matrices: Extremal Rays and Applications", journal = "Mathematical Methods of Operations Research (formerly Zeitschrift fur Operations Research)", volume = "42", number = "2", year = "1995", pages = "161-168" } @InProceedings{Sa05-conf, author = "Amir Said", title = "Efficient Alphabet Partitioning Algorithms for Low-Complexity Entropy Coding", booktitle = "Proceedings of the Data Compression Conference", year = "2005", pages = "183-192" } @Article{Sa06, author = "Yoshifumi Sakai", title = "A Linear Space Algorithm for Computing a Longest Common Increasing Subsequence", journal = "Information Processing Letters", volume = "99", number = "5", year = "2006", pages = "203-207" } @InProceedings{Sc95-conf, author = "Baruch Schieber", title = "Computing a Minimum-Weight $k$-Link Path in Graphs with the Concave {M}onge Property", booktitle = "Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms", year = "1995", pages = "405-411" } @Article{Sc98, author = "Baruch Schieber", title = "Computing a Minimum Weight $k$-Link Path in Graphs with the Concave {M}onge Property", journal = "Journal of Algorithms", volume = "29", number = "2", year = "1998", pages = "204-222", note = "A preliminary version appeared in \emph{Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms}, pages 405\---411, 1995." } @InProceedings{SeDu04+, author = "Joshua Senecal and Mark Duchaineau and Kenneth I. Joy", title = "Length-Limited Variable-to-Variable Length Codes for High-Performance Entropy Coding", booktitle = "Proceedings of the Data Compression Conference", year = "2004", pages = "389-398" } @PhdThesis{Sh02, author = "Rahul Shah", title = "Undiscretized Dynamic Programming and Ordinal Embeddings", school = "New Brunswick, Rutgers, the State University of New Jersey", year = "2002" } @InProceedings{ShFa02-conf, author = "Rahul Shah and Martin Farach-Colton", title = "Undiscretized Dynamic Programming: Faster Algorithms for Facility Location and Related Problems on Trees", booktitle = "Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms", year = "2002", pages = "108-115" } @Article{SrSc01+, author = "Anand Srivastav and Hartmut Schroeter and Christoph Michel", title = "Approximation Algorithms for Pick-and-Place Robots", journal = "Annals of Operations Research", volume = "107", number = "1\---4", year = "2001", pages = "321-338" } @article{Suri_linear_86, author = {Subhash Suri}, title = {A linear time algorithm for minimum link paths inside a simple polygon}, journal = {Computer Vision, Graphics and Image Processing}, volume = {35}, issue = {1}, month = {July}, year = {1986}, issn = {0734-189X}, pages = {99--110}, numpages = {12}, url = {http://portal.acm.org/citation.cfm?id=16504.16509}, doi = {10.1016/0734-189X(86)90127-1}, acmid = {16509}, publisher = {Academic Press Professional, Inc.}, address = {San Diego, CA, USA}, } @Article{Ta96, author = "Arie Tamir", title = "An ${O}(pn^2)$ Algorithm for the $p$-Median and Related Problems on Tree Graphs", journal = "Operations Research Letters", volume = "19", number = "2", year = "1996", pages = "59-64" } @article{Tiskin_Arxiv_09, author = {Alexandre Tiskin}, title = {Semi-local string comparison: algorithmic techniques and applications}, journal = {CoRR}, volume = {abs/0707.3619}, year = {2007}, ee = {http://arxiv.org/abs/0707.3619}, bibsource = {DBLP, http://dblp.uni-trier.de} } @InProceedings{TuMo96, author = "Andrew Turpin and Alistair Moffat", title = "Efficient Implementation of the Package-Merge Paradigm for Generating Length-Limited Codes", booktitle = "Proceedings of Computing: The Australasian Theory Symposium", year = "1996", pages = "187-195" } @Article{TuMo95, author = "Andrew Turpin and Alistair Moffat", title = "Practical Length-Limited Coding for Large Alphabets", journal = "The Computer Journal", volume = "38", number = "5", year = "1995", pages = "339-347" } @InProceedings{Va76, author = "Jan van Leeuwen", title = "On the Construction of Huffman Trees", booktitle = "Proceedings of the 3rd International Colloquium on Automata, Languages and Programming", year = "1976", pages = "382-410" } @Article{Wa89, author = "Michelle L. Wachs", title = "On an Efficient Dynamic Programming Technique of {F}. {F}. {Y}ao", journal = "Journal of Algorithms", volume = "10", number = "4", year = "1989", pages = "518-530" } @article{WaGe00, author = {Albert P. M. Wagelmans and A. E. Gerodimos}, title = {Improved dynamic programs for some batching problems involving the maximum lateness criterion}, journal = {Oper. Res. Lett.}, volume = {27}, number = {3}, year = {2000}, pages = {109-118}, ee = {http://dx.doi.org/10.1016/S0167-6377(00)00040-7}, bibsource = {DBLP, http://dblp.uni-trier.de} } @Article{WaFi74, author = "Robert A. Wagner and Michael J. Fischer", title = "The String-to-String Correction Problem", journal = "Journal of the ACM", volume = "21", number = "1", year = "1974", pages = "168-173" } @ARTICLE{WaZhLi2009, author={Fei-Yue Wang and Huaguang Zhang and Derong Liu}, journal={Computational Intelligence Magazine, IEEE}, title={Adaptive Dynamic Programming: An Introduction}, year={2009}, month=may , volume={4}, number={2}, pages={39 -47}, keywords={adaptive dynamic programming;approximate dynamic programming;convergence analysis;iterative algorithms;system stability;convergence of numerical methods;dynamic programming;iterative methods;}, doi={10.1109/MCI.2009.932261}, ISSN={1556-603X} } @PhdThesis{Weimann09, author = "Oren Weimann", title = "Accelerating Dynamic Programming", school = "MIT", year = "2009" } @Article{We76, author = "Russell L. Wessner", title = "Optimal Alphabetic Search Trees with Restricted Maximal Height", journal = "Information Processing Letters", volume = "4", number = "4", year = "1976", pages = "90-94" } @Article{Wi79, author = "A. Wikstrom", title = "Optimal Search Trees and Length Restricted Codes", journal = "BIT Numerical Mathematics", volume = "19", number = "4", year = "1979", pages = "518-524" } @Article{Wi88, author = "Robert Wilber", title = "The Concave Least-Weight Subsequence Problem Revisited", journal = "Journal of Algorithms", volume = "9", number = "3", year = "1988", pages = "418-425" } @article{DP_PTAS_Woe_05, title={{A comment on scheduling two parallel machines with capacity constraints}}, author={Woeginger, G.J.}, journal={Discrete Optimization}, volume={2}, number={3}, pages={269--272}, issn={1572-5286}, year={2005}, publisher={Elsevier} } @Article{Wo00, author = "Gerhard J. Woeginger", title = "Monge Strikes Again: Optimal Placement of Web Proxies in the {I}nternet", journal = "Operations Research Letters", volume = "27", number = "3", year = "2000", pages = "93-96" } @Article{Wu91, author = "Xiaolin Wu", title = "Optimal Quantization by Matrix Searching", journal = "Journal of Algorithms", volume = "12", number = "4", year = "1991", pages = "663-673" } @Article{YaHu05+, author = "I-Hsuan Yang and Chien-Pin Huang and Kun-Mao Chao", title = "A Fast Algorithm for Computing a Longest Common Increasing Subsequence", journal = "Information Processing Letters", volume = "93", number = "5", year = "2005", pages = "249-253" } @InProceedings{Ya80-conf, author = "F. Frances Yao", title = "Efficient Dynamic Programming Using Quadrangle Inequalities", booktitle = "Proceedings of the 12th Annual ACM Symposium on Theory of Computing", year = "1980", pages = "429-435" } @Article{Ya82, author = "F. Frances Yao", title = "Speed-up in Dynamic Programming", journal = "SIAM Journal on Matrix Analysis and Applications (formerly SIAM Journal on Algebraic and Discrete Methods)", volume = "3", number = "4", year = "1982", pages = "532-540" } @Article{ZhWa79, author = "Yongjin Zhu and Jianfang Wang", title = "On Alphabetic-Extended Binary Trees with Restricted Path Length", journal = "Scientia Sinica", volume = "22", year = "1979", pages = "1362-1371" }