IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v23y2012i1d10.1007_s10878-010-9341-7.html
   My bibliography  Save this article

A new approach to solve open-partition problems

Author

Listed:
  • Huilan Chang

    (National Chiao Tung University
    Rutgers University)

  • Frank K. Hwang
  • Uriel G. Rothblum

    (Technion)

Abstract

A partition problem in one-dimensional space is to seek a partition of a set of numbers that maximizes a given objective function. In some partition problems, the partition size, i.e., the number of nonempty parts in a partition, is fixed; while in others, the size can vary arbitrarily. We call the former the size-partition problem and the latter the open-partition problem. In general, it is much harder to solve open problems since the objective functions depend on size. In this paper, we propose a new approach by allowing empty parts and transform the open problem into a size problem allowing empty parts, called a relaxed-size problem. While the sortability theory has been established in the literature as a powerful tool to attack size partition problems, we develop the sortability theory for relaxed-size problems as a medium to solve open problems.

Suggested Citation

  • Huilan Chang & Frank K. Hwang & Uriel G. Rothblum, 2012. "A new approach to solve open-partition problems," Journal of Combinatorial Optimization, Springer, vol. 23(1), pages 61-78, January.
    • Handle: RePEc:spr:jcomop:v:23:y:2012:i:1:d:10.1007_s10878-010-9341-7
    DOI: 10.1007/s10878-010-9341-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-010-9341-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-010-9341-7?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. S. Anily & A. Federgruen, 1991. "Structured Partitioning Problems," Operations Research, INFORMS, vol. 39(1), pages 130-149, February.
    2. Chakravarty, Amiya K., 1982. "Inventory grouping for joint replenishment," Engineering Costs and Production Economics, Elsevier, vol. 7(1), pages 19-24, July.
    3. A. K. Chakravarty & J. B. Orlin & U. G. Rothblum, 1982. "Technical Note—A Partitioning Problem with Additive Objective with an Application to Optimal Inventory Groupings for Joint Replenishment," Operations Research, INFORMS, vol. 30(5), pages 1018-1022, October.
    4. Shmuel Gal & Boris Klots, 1995. "Optimal Partitioning Which Maximizes the Sum of the Weighted Averages," Operations Research, INFORMS, vol. 43(3), pages 500-508, June.
    Full references (including those not matched with items on IDEAS)

    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. Frank K. Hwang & Uriel G. Rothblum, 2011. "On the number of separable partitions," Journal of Combinatorial Optimization, Springer, vol. 21(4), pages 423-433, May.
    2. Chung‐Lun Li & Zhi‐Long Chen, 2006. "Bin‐packing problem with concave costs of bin utilization," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(4), pages 298-308, June.
    3. Gerard J. Chang & Fu-Loong Chen & Lingling Huang & Frank K. Hwang & Su-Tzu Nuan & Uriel G. Rothblum & I-Fan Sun & Jan-Wen Wang & Hong-Gwa Yeh, 1998. "Sortabilities of Partition Properties," Journal of Combinatorial Optimization, Springer, vol. 2(4), pages 413-427, December.
    4. Yaakov Malinovsky, 2019. "Sterrett Procedure for the Generalized Group Testing Problem," Methodology and Computing in Applied Probability, Springer, vol. 21(3), pages 829-840, September.
    5. Sheikh-Zadeh, Alireza & Rossetti, Manuel D. & Scott, Marc A., 2021. "Performance-based inventory classification methods for large-Scale multi-echelon replenishment systems," Omega, Elsevier, vol. 101(C).
    6. Siddhartha Syam & Bala Shetty, 1998. "Coordinated replenishments from multiple suppliers with price discounts," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(6), pages 579-598, September.
    7. Roy Cerqueti & Paolo Falbo & Cristian Pelizzari & Federica Ricca & Andrea Scozzari, 2012. "A Mixed Integer Linear Programming Approach to Markov Chain Bootstrapping," Working Papers 67-2012, Macerata University, Department of Finance and Economic Sciences, revised Nov 2012.
    8. Hrayer Aprahamian & Douglas R. Bish & Ebru K. Bish, 2019. "Optimal Risk-Based Group Testing," Management Science, INFORMS, vol. 65(9), pages 4365-4384, September.
    9. Ho, Sin C. & Szeto, W.Y. & Kuo, Yong-Hong & Leung, Janny M.Y. & Petering, Matthew & Tou, Terence W.H., 2018. "A survey of dial-a-ride problems: Literature review and recent developments," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 395-421.
    10. Cerqueti, Roy & Falbo, Paolo & Guastaroba, Gianfranco & Pelizzari, Cristian, 2013. "A Tabu Search heuristic procedure in Markov chain bootstrapping," European Journal of Operational Research, Elsevier, vol. 227(2), pages 367-384.
    11. Wildeman, R. E. & Dekker, R. & Smit, A. C. J. M., 1997. "A dynamic policy for grouping maintenance activities," European Journal of Operational Research, Elsevier, vol. 99(3), pages 530-551, June.
    12. Kumar Satyendra & Venkata Rao, V. & Tirupati Devanath, 2003. "A heuristic procedure for one dimensional bin packing problem with additional constraints," IIMA Working Papers WP2003-11-02, Indian Institute of Management Ahmedabad, Research and Publication Department.
    13. Ogawa, Sanae & Ohta, Hiroshi, 1995. "Common order cycle system for multi-item inventory model with learning in ordering and transportation," International Journal of Production Economics, Elsevier, vol. 41(1-3), pages 321-325, October.
    14. Hrayer Aprahamian & Hadi El-Amine, 2022. "Optimal Screening of Populations with Heterogeneous Risk Profiles Under the Availability of Multiple Tests," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 150-164, January.
    15. Hussein El Hajj & Douglas R. Bish & Ebru K. Bish & Denise M. Kay, 2022. "Novel Pooling Strategies for Genetic Testing, with Application to Newborn Screening," Management Science, INFORMS, vol. 68(11), pages 7994-8014, November.
    16. Arbib, Claudio & Rossi, Fabrizio, 2000. "An optimization problem arising in the design of multiring systems," European Journal of Operational Research, Elsevier, vol. 124(1), pages 63-76, July.
    17. Inniss, Tasha R., 2006. "Seasonal clustering technique for time series data," European Journal of Operational Research, Elsevier, vol. 175(1), pages 376-384, November.
    18. N H Moin & S Salhi, 2007. "Inventory routing problems: a logistical overview," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(9), pages 1185-1194, September.
    19. Joseph, Anito & Bryson, Noel, 1998. "Parametric linear programming and cluster analysis," European Journal of Operational Research, Elsevier, vol. 111(3), pages 582-588, December.
    20. Chakravarty, A. K. & Orlin, James B., 1953-. & Rothblum, U. G., 1982. "Consecutive optimizors for a partitioning problem with applications to optimal inventory groupings for joint replenishment," Working papers 1383-82., Massachusetts Institute of Technology (MIT), Sloan School of Management.

    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:jcomop:v:23:y:2012:i:1:d:10.1007_s10878-010-9341-7. 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.