Fast Algorithms with Algebraic Monge Properties | SpringerLink
Skip to main content
Springer Nature Link
Log in

Fast Algorithms with Algebraic Monge Properties

  • Conference paper
  • First Online:
Mathematical Foundations of Computer Science 2002 (MFCS 2002)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2420))

  • 521 Accesses

Abstract

When restricted to cost arrays possessing the sum Monge property, many combinatorial optimization problems with sum objective functions become significantly easier to solve. The more general algebraic assignment and transportation problems are similarly easier to solve given cost arrays possessing the corresponding algebraic Monge property. We show that Monge-array results for two sum-of-edge-costs shortest-path problems can likewise be extended to a general algebraic setting, provided the problems’ ordered commutative semigroup satisfies one additional restriction. In addition to this general result, we also show how our algorithms can be modified to solve certain bottleneck shortest-path problems, even though the ordered commutative semigroup naturally associated with bottleneck problems does not satisfy our additional restriction. We show how our bottleneck shortest-path techniques can be used to obtain fast algorithms for a variant of Hirschberg and Larmore’s optimal paragraph formation problem, and a special case of the bottleneck traveling-salesman problem.

Conference Version.

Research of these authors supported by NSF grant CCR-9821009.

This author’s work was done while the author was at Sandia National Laboratories, and supported by the U.S. Department of Energy under Contract DE-AC04-76DP00789.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2(2):195–208, 1987.

    Article  MATH  MathSciNet  Google Scholar 

  2. P. K. Agarwal and S. Sen. Selection in monotone matrices and computing k th nearest neighbors. In Proceedings of the 4th Scandinavian Workshop on Algorithm Theory, 1994.

    Google Scholar 

  3. A. Aggarwal, B. Schieber, and T. Tokuyama. Finding a minimum weight k-link path in graphs with Monge property and applications. In Proc. 9th Annu. ACM Sympos. Comput. Geom., pages 189–197, 1993.

    Google Scholar 

  4. A. Aggarwal, B. Schieber, and T. Tokuyama. Finding a minimum-weight k-link path in graphs with the concave Monge property and applications. Discrete Comput. Geom., 12:263–280, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  5. R. E. Burkard and W. Sandholzer. Efficiently solvable special cases of bottleneck travelling salesman problems. Discrete Applied Mathematics, 32(1):61–76, 1991.

    Article  MATH  MathSciNet  Google Scholar 

  6. R. E. Burkard. Remarks on some scheduling problems with algebraic objective functions. Operations Research Verfahren, 32:63–77, 1979.

    MATH  Google Scholar 

  7. R. E. Burkard and U. Zimmermann. Combinatorial optimization in linearly ordered semimodules: A survey. In B. Korte, editor, Modern Applied Mathematics: Optimization and Operations Research, pages 391–436. North-Holland Publishing Company, Amsterdam, Holland, 1982.

    Google Scholar 

  8. R. E. Burkard and B. Klinz and R. Rudolf. Perspectives of monge properties in optimization. Discrete Applied Mathematics, 70:95–161, 1996.

    Article  MATH  MathSciNet  Google Scholar 

  9. G. N. Frederickson and D. B. Johnson. The complexity of selection and ranking in X + Y and matrices with sorted columns. Journal of Computer and System Sciences, 24(4):197–208, 1982.

    Article  MATH  MathSciNet  Google Scholar 

  10. H. N. Gabow and R. E. Tarjan. Algorithms for two bottleneck optimization problems. Journal of Algorithms, 9(3):411–417, 1988.

    Article  MATH  MathSciNet  Google Scholar 

  11. D. S. Hirschberg and L. L. Larmore. The least weight subsequence problem. SIAM Journal on Computing, 16(4):628–638, 1987.

    Article  MATH  MathSciNet  Google Scholar 

  12. D. S. Hirschberg and D. J. Volper. Improved update/query algorithms for the interval valuation problem. Information Processing Letters, 24:307–310, 1987.

    Article  Google Scholar 

  13. A.J. Hoffman. On simple linear programming problems. In Convexity, Proc. Symposia in Pure Mathematics, volume 7, pages 317–327, Providence, RI, 1961. American Mathematical Society.

    Google Scholar 

  14. B. Klinz, R. Rudolf, and G.J. Woeginger. On the recognition of bottleneck monge matrices. Discrete Applied Mathematics, 63:43–74, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  15. L. L. Larmore and B. Schieber. On-line dynamic programming with applications to the prediction of RNA secondary structure. Journal of Algorithms, 12(3):490–515, 1991.

    Article  MATH  MathSciNet  Google Scholar 

  16. E. Seiffart. Algebraic transportation and assignment problems with “Monge-property” and “quasi-convexity”. Discrete Applied Mathematics, 1993.

    Google Scholar 

  17. R. Wilber. The concave least-weight subsequence problem revisited. Journal of Algorithms, 9 3):418–425, 1988.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Nevada, Las Vegas, Nevada, 89154, USA

    Wolfgang W. Bein & Lawrence L. Larmore

  2. Universität Osnabrück, Fachbereich Mathematik/Informatik, D-49069, Osnabrück, Germany

    Peter Brucker

  3. Bremer Associates, Inc., 215 First Street, Cambridge, Massachusetts, 02142, USA

    James K. Park

Authors
  1. Wolfgang W. Bein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peter Brucker
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lawrence L. Larmore
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. James K. Park
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institute of Informatics, Warsaw University, ul. Banacha 2, 02-097, Warszawa, Poland

    Krzysztof Diks  & Wojciech Rytter  & 

  2. Department of Computer Science, Liverpool University, Peach Street, Liverpool, L69 7ZF, UK

    Wojciech Rytter

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bein, W.W., Brucker, P., Larmore, L.L., Park, J.K. (2002). Fast Algorithms with Algebraic Monge Properties. In: Diks, K., Rytter, W. (eds) Mathematical Foundations of Computer Science 2002. MFCS 2002. Lecture Notes in Computer Science, vol 2420. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45687-2_8

Download citation

  • DOI: https://doi.org/10.1007/3-540-45687-2_8

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-44040-6

  • Online ISBN: 978-3-540-45687-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation