Parameterized Algorithms for the 2-Clustering Problem with Minimum Sum and Minimum Sum of Squares Objective Functions View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2014-02-07

AUTHORS

Bang Ye Wu, Li-Hsuan Chen

ABSTRACT

In the Min-Sum 2-Clustering problem, we are given a graph and a parameter k, and the goal is to determine if there exists a 2-partition of the vertex set such that the total conflict number is at most k, where the conflict number of a vertex is the number of its non-neighbors in the same cluster and neighbors in the different cluster. The problem is equivalent to 2-Cluster Editing and 2-Correlation Clustering with an additional multiplicative factor two in the cost function. In this paper we show an algorithm for Min-Sum 2-Clustering with time complexity O(n⋅2.619r/(1−4r/n)+n3), where n is the number of vertices and r=k/n. Particularly, the time complexity is O∗(2.619k/n) for k∈o(n2) and polynomial for k∈O(nlogn), which implies that the problem can be solved in subexponential time for k∈o(n2). We also design a parameterized algorithm for a variant in which the cost is the sum of the squared conflict-numbers. For k∈o(n3), the algorithm runs in subexponential O(n3⋅5.171θ) time, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\theta=\sqrt{k/n}$\end{document}. More... »

PAGES

818-835

References to SciGraph publications

  • 2009. Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms in PARAMETERIZED AND EXACT COMPUTATION
  • 2003-05-13. Graph-Modeled Data Clustering: Fixed-Parameter Algorithms for Clique Generation in ALGORITHMS AND COMPLEXITY
  • 2004-03-19. Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems in ALGORITHMICA
  • 2010. Exact Exponential Algorithms in NONE
  • 2008-07-16. Fixed-Parameter Enumerability of Cluster Editing and Related Problems in THEORY OF COMPUTING SYSTEMS
  • 2008-10-15. Fixed-Parameter Algorithms for Cluster Vertex Deletion in THEORY OF COMPUTING SYSTEMS
  • 2004-07. Correlation Clustering in MACHINE LEARNING
  • 1999. Parameterized Complexity in NONE
  • 2013. On the Min-Max 2-Cluster Editing Problem in ADVANCES IN INTELLIGENT SYSTEMS AND APPLICATIONS - VOLUME 1
  • 2007-01-01. Optimal Edge Deletions for Signed Graph Balancing in EXPERIMENTAL ALGORITHMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-014-9874-8

    DOI

    http://dx.doi.org/10.1007/s00453-014-9874-8

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1051438401


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC", 
              "id": "http://www.grid.ac/institutes/grid.412047.4", 
              "name": [
                "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wu", 
            "givenName": "Bang Ye", 
            "id": "sg:person.013045767237.23", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC", 
              "id": "http://www.grid.ac/institutes/grid.412047.4", 
              "name": [
                "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chen", 
            "givenName": "Li-Hsuan", 
            "id": "sg:person.014055212561.22", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055212561.22"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-35452-6_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032367522", 
              "https://doi.org/10.1007/978-3-642-35452-6_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-0515-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050354225", 
              "https://doi.org/10.1007/978-1-4612-0515-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-008-9150-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032458581", 
              "https://doi.org/10.1007/s00224-008-9150-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-16533-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012209190", 
              "https://doi.org/10.1007/978-3-642-16533-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44849-7_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000170504", 
              "https://doi.org/10.1007/3-540-44849-7_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/b:mach.0000033116.57574.95", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005313049", 
              "https://doi.org/10.1023/b:mach.0000033116.57574.95"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-008-9130-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035666083", 
              "https://doi.org/10.1007/s00224-008-9130-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-004-1090-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051624082", 
              "https://doi.org/10.1007/s00453-004-1090-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-11269-0_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022401414", 
              "https://doi.org/10.1007/978-3-642-11269-0_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-72845-0_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026860505", 
              "https://doi.org/10.1007/978-3-540-72845-0_23"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2014-02-07", 
        "datePublishedReg": "2014-02-07", 
        "description": "In the Min-Sum 2-Clustering problem, we are given a graph and a parameter k, and the goal is to determine if there exists a 2-partition of the vertex set such that the total conflict number is at most k, where the conflict number of a vertex is the number of its non-neighbors in the same cluster and neighbors in the different cluster. The problem is equivalent to 2-Cluster Editing and 2-Correlation Clustering with an additional multiplicative factor two in the cost function. In this paper we show an algorithm for Min-Sum 2-Clustering with time complexity O(n\u22c52.619r/(1\u22124r/n)+n3), where n is the number of vertices and r=k/n. Particularly, the time complexity is O\u2217(2.619k/n) for k\u2208o(n2) and polynomial for k\u2208O(nlogn), which implies that the problem can be solved in subexponential time for k\u2208o(n2). We also design a parameterized algorithm for a variant in which the cost is the sum of the squared conflict-numbers. For k\u2208o(n3), the algorithm runs in subexponential O(n3\u22c55.171\u03b8) time, where \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\theta=\\sqrt{k/n}$\\end{document}.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00453-014-9874-8", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "72"
          }
        ], 
        "keywords": [
          "time complexity", 
          "minimum sum", 
          "conflict number", 
          "subexponential time", 
          "number of vertices", 
          "algorithm", 
          "same cluster", 
          "cost function", 
          "objective function", 
          "different clusters", 
          "squares objective function", 
          "complexity", 
          "vertices", 
          "graph", 
          "neighbors", 
          "editing", 
          "clusters", 
          "number", 
          "cost", 
          "parameter k", 
          "goal", 
          "sum", 
          "time", 
          "polynomials", 
          "factor two", 
          "function", 
          "variants", 
          "two", 
          "problem", 
          "paper", 
          "Min-Sum 2-Clustering problem", 
          "total conflict number", 
          "additional multiplicative factor two", 
          "multiplicative factor two", 
          "Min-Sum 2-Clustering"
        ], 
        "name": "Parameterized Algorithms for the 2-Clustering Problem with Minimum Sum and Minimum Sum of Squares Objective Functions", 
        "pagination": "818-835", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1051438401"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-014-9874-8"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-014-9874-8", 
          "https://app.dimensions.ai/details/publication/pub.1051438401"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:32", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_641.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00453-014-9874-8"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9874-8'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9874-8'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9874-8'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9874-8'


     

    This table displays all metadata directly associated to this object as RDF triples.

    140 TRIPLES      22 PREDICATES      70 URIs      52 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-014-9874-8 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N02eeb60c500d4178854227730e40b465
    4 schema:citation sg:pub.10.1007/3-540-44849-7_17
    5 sg:pub.10.1007/978-1-4612-0515-9
    6 sg:pub.10.1007/978-3-540-72845-0_23
    7 sg:pub.10.1007/978-3-642-11269-0_8
    8 sg:pub.10.1007/978-3-642-16533-7
    9 sg:pub.10.1007/978-3-642-35452-6_16
    10 sg:pub.10.1007/s00224-008-9130-1
    11 sg:pub.10.1007/s00224-008-9150-x
    12 sg:pub.10.1007/s00453-004-1090-5
    13 sg:pub.10.1023/b:mach.0000033116.57574.95
    14 schema:datePublished 2014-02-07
    15 schema:datePublishedReg 2014-02-07
    16 schema:description In the Min-Sum 2-Clustering problem, we are given a graph and a parameter k, and the goal is to determine if there exists a 2-partition of the vertex set such that the total conflict number is at most k, where the conflict number of a vertex is the number of its non-neighbors in the same cluster and neighbors in the different cluster. The problem is equivalent to 2-Cluster Editing and 2-Correlation Clustering with an additional multiplicative factor two in the cost function. In this paper we show an algorithm for Min-Sum 2-Clustering with time complexity O(n⋅2.619r/(1−4r/n)+n3), where n is the number of vertices and r=k/n. Particularly, the time complexity is O∗(2.619k/n) for k∈o(n2) and polynomial for k∈O(nlogn), which implies that the problem can be solved in subexponential time for k∈o(n2). We also design a parameterized algorithm for a variant in which the cost is the sum of the squared conflict-numbers. For k∈o(n3), the algorithm runs in subexponential O(n3⋅5.171θ) time, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\theta=\sqrt{k/n}$\end{document}.
    17 schema:genre article
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf N1d466c6c043344968396150ed1aca829
    21 Ne6dac30428a54a129c338db701a3d3f0
    22 sg:journal.1047644
    23 schema:keywords Min-Sum 2-Clustering
    24 Min-Sum 2-Clustering problem
    25 additional multiplicative factor two
    26 algorithm
    27 clusters
    28 complexity
    29 conflict number
    30 cost
    31 cost function
    32 different clusters
    33 editing
    34 factor two
    35 function
    36 goal
    37 graph
    38 minimum sum
    39 multiplicative factor two
    40 neighbors
    41 number
    42 number of vertices
    43 objective function
    44 paper
    45 parameter k
    46 polynomials
    47 problem
    48 same cluster
    49 squares objective function
    50 subexponential time
    51 sum
    52 time
    53 time complexity
    54 total conflict number
    55 two
    56 variants
    57 vertices
    58 schema:name Parameterized Algorithms for the 2-Clustering Problem with Minimum Sum and Minimum Sum of Squares Objective Functions
    59 schema:pagination 818-835
    60 schema:productId N074e434b8b2442d198d512497480c20f
    61 N8a2b997fdc8843bdb504347f4b38fb2b
    62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051438401
    63 https://doi.org/10.1007/s00453-014-9874-8
    64 schema:sdDatePublished 2021-12-01T19:32
    65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    66 schema:sdPublisher N21b3f21e4e514fc980d8695ddbb592a6
    67 schema:url https://doi.org/10.1007/s00453-014-9874-8
    68 sgo:license sg:explorer/license/
    69 sgo:sdDataset articles
    70 rdf:type schema:ScholarlyArticle
    71 N02eeb60c500d4178854227730e40b465 rdf:first sg:person.013045767237.23
    72 rdf:rest Nb74c2b7976e34b69a48f48a834454c75
    73 N074e434b8b2442d198d512497480c20f schema:name dimensions_id
    74 schema:value pub.1051438401
    75 rdf:type schema:PropertyValue
    76 N1d466c6c043344968396150ed1aca829 schema:volumeNumber 72
    77 rdf:type schema:PublicationVolume
    78 N21b3f21e4e514fc980d8695ddbb592a6 schema:name Springer Nature - SN SciGraph project
    79 rdf:type schema:Organization
    80 N8a2b997fdc8843bdb504347f4b38fb2b schema:name doi
    81 schema:value 10.1007/s00453-014-9874-8
    82 rdf:type schema:PropertyValue
    83 Nb74c2b7976e34b69a48f48a834454c75 rdf:first sg:person.014055212561.22
    84 rdf:rest rdf:nil
    85 Ne6dac30428a54a129c338db701a3d3f0 schema:issueNumber 3
    86 rdf:type schema:PublicationIssue
    87 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Information and Computing Sciences
    89 rdf:type schema:DefinedTerm
    90 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Artificial Intelligence and Image Processing
    92 rdf:type schema:DefinedTerm
    93 sg:journal.1047644 schema:issn 0178-4617
    94 1432-0541
    95 schema:name Algorithmica
    96 schema:publisher Springer Nature
    97 rdf:type schema:Periodical
    98 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4
    99 schema:familyName Wu
    100 schema:givenName Bang Ye
    101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
    102 rdf:type schema:Person
    103 sg:person.014055212561.22 schema:affiliation grid-institutes:grid.412047.4
    104 schema:familyName Chen
    105 schema:givenName Li-Hsuan
    106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055212561.22
    107 rdf:type schema:Person
    108 sg:pub.10.1007/3-540-44849-7_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000170504
    109 https://doi.org/10.1007/3-540-44849-7_17
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/978-1-4612-0515-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050354225
    112 https://doi.org/10.1007/978-1-4612-0515-9
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/978-3-540-72845-0_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026860505
    115 https://doi.org/10.1007/978-3-540-72845-0_23
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/978-3-642-11269-0_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022401414
    118 https://doi.org/10.1007/978-3-642-11269-0_8
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/978-3-642-16533-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012209190
    121 https://doi.org/10.1007/978-3-642-16533-7
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/978-3-642-35452-6_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032367522
    124 https://doi.org/10.1007/978-3-642-35452-6_16
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/s00224-008-9130-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035666083
    127 https://doi.org/10.1007/s00224-008-9130-1
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/s00224-008-9150-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1032458581
    130 https://doi.org/10.1007/s00224-008-9150-x
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/s00453-004-1090-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051624082
    133 https://doi.org/10.1007/s00453-004-1090-5
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1023/b:mach.0000033116.57574.95 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005313049
    136 https://doi.org/10.1023/b:mach.0000033116.57574.95
    137 rdf:type schema:CreativeWork
    138 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, 621, ChiaYi, Taiwan, ROC
    139 schema:name National Chung Cheng University, 621, ChiaYi, Taiwan, ROC
    140 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...