IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v206y2010i3p547-554.html
   My bibliography  Save this article

Min sum clustering with penalties

Author

Listed:
  • Hassin, Refael
  • Or, Einat

Abstract

Given a complete graph G=(V,E), a weight function on its edges, and a penalty function on its vertices, the penalized k-min-sum problem is the problem of finding a partition of V to k+1 sets, S1,...,Sk+1, minimizing , where for , and p(S)=[summation operator]i[set membership, variant]Spi. Our main result is a randomized approximation scheme for the metric version of the penalized 1-min-sum problem, when the ratio between the minimal and maximal penalty is bounded. For the metric penalized k-min-sum problem where k is a constant, we offer a 2-approximation.

Suggested Citation

  • Hassin, Refael & Or, Einat, 2010. "Min sum clustering with penalties," European Journal of Operational Research, Elsevier, vol. 206(3), pages 547-554, November.
    • Handle: RePEc:eee:ejores:v:206:y:2010:i:3:p:547-554
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00172-4
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Chen, Yen-Liang & Hu, Hui-Ling, 2006. "An overlapping cluster algorithm to provide non-exhaustive clustering," European Journal of Operational Research, Elsevier, vol. 173(3), pages 762-780, September.
    2. Hochbaum, Dorit S., 2002. "Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations," European Journal of Operational Research, Elsevier, vol. 140(2), pages 291-321, 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. Rota Bulò, Samuel & Pelillo, Marcello, 2017. "Dominant-set clustering: A review," European Journal of Operational Research, Elsevier, vol. 262(1), pages 1-13.

    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. Armbruster, Benjamin & Smith, J. Cole & Park, Kihong, 2007. "A packet filter placement problem with application to defense against spoofed denial of service attacks," European Journal of Operational Research, Elsevier, vol. 176(2), pages 1283-1292, January.
    2. Roberto Asín Achá & Dorit S. Hochbaum & Quico Spaen, 2020. "HNCcorr: combinatorial optimization for neuron identification," Annals of Operations Research, Springer, vol. 289(1), pages 5-32, June.
    3. Xu, Xuelian & Liu, Xiaodong & Chen, Yan, 2009. "Applications of axiomatic fuzzy set clustering method on management strategic analysis," European Journal of Operational Research, Elsevier, vol. 198(1), pages 297-304, October.
    4. Baumann, P. & Hochbaum, D.S. & Yang, Y.T., 2019. "A comparative study of the leading machine learning techniques and two new optimization algorithms," European Journal of Operational Research, Elsevier, vol. 272(3), pages 1041-1057.
    5. Liao, Pin-Chao & Zhang, Kenan & Wang, Tao & Wang, Yanqing, 2016. "Integrating bibliometrics and roadmapping: A case of strategic promotion for the ground source heat pump in China," Renewable and Sustainable Energy Reviews, Elsevier, vol. 57(C), pages 292-301.
    6. Meisel, Stephan & Mattfeld, Dirk, 2010. "Synergies of Operations Research and Data Mining," European Journal of Operational Research, Elsevier, vol. 206(1), pages 1-10, October.
    7. Jia-Yen Huang & Rong-Chang Chen, 2019. "Exploring the intellectual structure of cloud patents using non-exhaustive overlaps," Scientometrics, Springer;Akadémiai Kiadó, vol. 121(2), pages 739-769, November.
    8. Julian Rossbroich & Jeffrey Durieux & Tom F. Wilderjans, 2022. "Model Selection Strategies for Determining the Optimal Number of Overlapping Clusters in Additive Overlapping Partitional Clustering," Journal of Classification, Springer;The Classification Society, vol. 39(2), pages 264-301, July.
    9. 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.
    10. Sabyasachi Guharay & KC Chang & Jie Xu, 2017. "Robust Estimation of Value-at-Risk through Distribution-Free and Parametric Approaches Using the Joint Severity and Frequency Model: Applications in Financial, Actuarial, and Natural Calamities Domain," Risks, MDPI, vol. 5(3), pages 1-30, July.

    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:eee:ejores:v:206:y:2010:i:3:p:547-554. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.