IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v117y2003i3d10.1023_a1023901806339.html
   My bibliography  Save this article

Least Squares Isotonic Regression in Two Dimensions

Author

Listed:
  • J. Spouge

    (National Institutes of Health)

  • H. Wan

    (National Center for Genome Resources)

  • W.J. Wilbur

    (National Institutes of Health)

Abstract

Given a finite partially-ordered set with a positive weighting function defined on its points, it is well known that any real-valued function defined on the set has a unique best order-preserving approximation in the weighted least squares sense. Many algorithms have been given for the solution of this isotonic regression problem. Most such algorithms either are not polynomial or they are of unknown time complexity. Recently, it has become clear that the general isotonic regression problem can be solved as a network flow problem in time O(n4) with a space requirement of O(n2), where n is the number of points in the set. Building on the insights at the basis of this improvement, we show here that, in the case of a general two-dimensional partial ordering, the problem can be solved in O(n3) time and, when the two-dimensional set is restricted to a grid, the time can be further improved to O(n2).

Suggested Citation

  • J. Spouge & H. Wan & W.J. Wilbur, 2003. "Least Squares Isotonic Regression in Two Dimensions," Journal of Optimization Theory and Applications, Springer, vol. 117(3), pages 585-605, June.
    • Handle: RePEc:spr:joptap:v:117:y:2003:i:3:d:10.1023_a:1023901806339
    DOI: 10.1023/A:1023901806339
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1023901806339
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1023/A:1023901806339?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. William L. Maxwell & John A. Muckstadt, 1985. "Establishing Consistent and Realistic Reorder Intervals in Production-Distribution Systems," Operations Research, INFORMS, vol. 33(6), pages 1316-1341, December.
    2. Jean-Claude Picard, 1976. "Maximal Closure of a Graph and Applications to Combinatorial Problems," Management Science, INFORMS, vol. 22(11), pages 1268-1272, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Oleg Burdakov & Oleg Sysoev, 2017. "A Dual Active-Set Algorithm for Regularized Monotonic Regression," Journal of Optimization Theory and Applications, Springer, vol. 172(3), pages 929-949, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dorit S. Hochbaum, 2004. "50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today," Management Science, INFORMS, vol. 50(6), pages 709-723, June.
    2. Rafael Epstein & Marcel Goic & Andrés Weintraub & Jaime Catalán & Pablo Santibáñez & Rodolfo Urrutia & Raúl Cancino & Sergio Gaete & Augusto Aguayo & Felipe Caro, 2012. "Optimizing Long-Term Production Plans in Underground and Open-Pit Copper Mines," Operations Research, INFORMS, vol. 60(1), pages 4-17, February.
    3. Kevin H. Shang & Jing-Sheng Song & Paul H. Zipkin, 2009. "Coordination Mechanisms in Decentralized Serial Inventory Systems with Batch Ordering," Management Science, INFORMS, vol. 55(4), pages 685-695, April.
    4. Luca Bertazzi & Maria Grazia Speranza, 1999. "Minimizing logistic costs in multistage supply chains," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(4), pages 399-417, June.
    5. Chatterjee, Snehamoy & Sethi, Manas Ranjan & Asad, Mohammad Waqar Ali, 2016. "Production phase and ultimate pit limit design under commodity price uncertainty," European Journal of Operational Research, Elsevier, vol. 248(2), pages 658-667.
    6. Biswas, Pritam & Sinha, Rabindra Kumar & Sen, Phalguni, 2023. "A review of state-of-the-art techniques for the determination of the optimum cut-off grade of a metalliferous deposit with a bibliometric mapping in a surface mine planning context," Resources Policy, Elsevier, vol. 83(C).
    7. Gary Kochenberger & Jin-Kao Hao & Fred Glover & Mark Lewis & Zhipeng Lü & Haibo Wang & Yang Wang, 2014. "The unconstrained binary quadratic programming problem: a survey," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 58-81, July.
    8. Adeinat, Hamza & Pazhani, Subramanian & Mendoza, Abraham & Ventura, Jose A., 2022. "Coordination of pricing and inventory replenishment decisions in a supply chain with multiple geographically dispersed retailers," International Journal of Production Economics, Elsevier, vol. 248(C).
    9. Luca Bertazzi & Maria Grazia Speranza & Walter Ukovich, 2000. "Exact and Heuristic Solutions for a Shipment Problem with Given Frequencies," Management Science, INFORMS, vol. 46(7), pages 973-988, July.
    10. Csapó, Gergely & Müller, Rudolf, 2013. "Optimal mechanism design for the private supply of a public good," Games and Economic Behavior, Elsevier, vol. 80(C), pages 229-242.
    11. Bertazzi, Luca & Grazia Speranza, Maria, 2005. "Worst-case analysis of the full load policy in the single link problem," International Journal of Production Economics, Elsevier, vol. 93(1), pages 217-224, January.
    12. Domenico Moramarco & Umutcan Salman, 2023. "Equal opportunities in many-to-one matching markets," Working Papers 649, ECINEQ, Society for the Study of Economic Inequality.
    13. Chu, Chi-Leung & Leon, V. Jorge, 2008. "Power-of-two single-warehouse multi-buyer inventory coordination with private information," International Journal of Production Economics, Elsevier, vol. 111(2), pages 562-574, February.
    14. Dorit S. Hochbaum, 2003. "Efficient Algorithms for the Inverse Spanning-Tree Problem," Operations Research, INFORMS, vol. 51(5), pages 785-797, October.
    15. Esmaeili, Ahmadreza & Hamidi, Jafar Khademi & Mousavi, Amin, 2023. "Determination of sublevel stoping layout using a network flow algorithm and the MRMR classification system," Resources Policy, Elsevier, vol. 80(C).
    16. Mark Goh & Ou Jihong & Teo Chung‐Piaw, 2001. "Warehouse sizing to minimize inventory and storage costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(4), pages 299-312, June.
    17. Chung-Piaw Teo & Dimitris Bertsimas, 2001. "Multistage Lot Sizing Problems via Randomized Rounding," Operations Research, INFORMS, vol. 49(4), pages 599-608, August.
    18. Nancel-Penard, Pierre & Morales, Nelson & Cornillier, Fabien, 2022. "A recursive time aggregation-disaggregation heuristic for the multidimensional and multiperiod precedence-constrained knapsack problem: An application to the open-pit mine block sequencing problem," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1088-1099.
    19. Jélvez, Enrique & Morales, Nelson & Nancel-Penard, Pierre & Peypouquet, Juan & Reyes, Patricio, 2016. "Aggregation heuristic for the open-pit block scheduling problem," European Journal of Operational Research, Elsevier, vol. 249(3), pages 1169-1177.
    20. Pavlos Eirinakis & Dimitrios Magos & Ioannis Mourtos & Panayiotis Miliotis, 2012. "Finding All Stable Pairs and Solutions to the Many-to-Many Stable Matching Problem," INFORMS Journal on Computing, INFORMS, vol. 24(2), pages 245-259, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:117:y:2003:i:3:d:10.1023_a:1023901806339. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.