IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v21y2011i4d10.1007_s10878-009-9263-4.html
   My bibliography  Save this article

On the number of separable partitions

Author

Listed:
  • Frank K. Hwang
  • Uriel G. Rothblum

    (Technion-Israel Institute of Technology)

Abstract

Consider partitions of a given set A of n distinct points in general position in ℝ d into parts where each pair of parts can be separated by a hyperplane that contains a given set of points E. We consider the problem of counting and generating all such partitions (correcting a classic 1967 result of Harding about the number of such partitions into two parts). Applications of the result to partition problems are presented.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jcomop:v:21:y:2011:i:4:d:10.1007_s10878-009-9263-4
    DOI: 10.1007/s10878-009-9263-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-009-9263-4
    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-009-9263-4?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. Shmuel Onn & Leonard J. Schulman, 2001. "The Vector Partition Problem for Convex Objective Functions," Mathematics of Operations Research, INFORMS, vol. 26(3), pages 583-590, August.
    2. 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.
    3. A. K. Chakravarty & J. B. Orlin & U. G. Rothblum, 1985. "Consecutive Optimizers for a Partitioning Problem with Applications to Optimal Inventory Groupings for Joint Replenishment," Operations Research, INFORMS, vol. 33(4), pages 820-834, August.
    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.
    5. Chakravarty, Amiya K., 1982. "Inventory grouping for joint replenishment," Engineering Costs and Production Economics, Elsevier, vol. 7(1), pages 19-24, July.
    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Jia Shu & Chung-Piaw Teo & Zuo-Jun Max Shen, 2005. "Stochastic Transportation-Inventory Network Design Problem," Operations Research, INFORMS, vol. 53(1), pages 48-60, February.
    6. Frank K. Hwang & Shmuel Onn & Uriel G. Rothblum, 2000. "Explicit solution of partitioning problems over a 1‐dimensional parameter space," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(6), pages 531-540, September.
    7. Yann Braouezec, 2013. "The Welfare Effects of Regulating the Number of Market Segments," Working Papers 2013-ECO-11, IESEG School of Management.
    8. Braouezec, Yann, 2016. "On the welfare effects of regulating the number of discriminatory prices," Research in Economics, Elsevier, vol. 70(4), pages 588-607.
    9. 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).
    10. 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.
    11. 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.
    12. 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.
    13. Borgwardt, S. & Brieden, A. & Gritzmann, P., 2017. "An LP-based k-means algorithm for balancing weighted point sets," European Journal of Operational Research, Elsevier, vol. 263(2), pages 349-355.
    14. Amiya K. Chakravarty & G. E. Martin, 1989. "Discount pricing policies for inventories subject to declining demand," Naval Research Logistics (NRL), John Wiley & Sons, vol. 36(1), pages 89-102, February.
    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. 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.
    18. Hrayer Aprahamian & Douglas R. Bish & Ebru K. Bish, 2019. "Optimal Risk-Based Group Testing," Management Science, INFORMS, vol. 65(9), pages 4365-4384, September.
    19. 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.
    20. Shmuel Onn & Uriel G. Rothblum, 2007. "The use of edge-directions and linear programming to enumerate vertices," Journal of Combinatorial Optimization, Springer, vol. 14(2), pages 153-164, October.

    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:21:y:2011:i:4:d:10.1007_s10878-009-9263-4. 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.