Ontology type: schema:ScholarlyArticle
2020-02-17
AUTHORSGuangting Chen, Yong Chen, Zhi-Zhong Chen, Guohui Lin, Tian Liu, An Zhang
ABSTRACTGiven a vertex-weighted connected graph G=(V,E,w(·))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = (V, E, w(\cdot ))$$\end{document}, the maximally balanced connected graphk-partition (k-BGP) seeks to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected and the weights of these k parts are as balanced as possible. When the concrete objective is to maximize the minimum (to minimize the maximum, respectively) weight of the k parts, the problem is denoted as max–mink-BGP (min–maxk-BGP, respectively), and has received much study since about four decades ago. On general graphs, max–mink-BGP is strongly NP-hard for every fixed k≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 2$$\end{document}, and remains NP-hard even for the vertex uniformly weighted case; when k is part of the input, the problem is denoted as max–min BGP, and cannot be approximated within 6/5 unless P =\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$=$$\end{document} NP. In this paper, we study the tripartition problems from approximation algorithms perspective and present a 3/2-approximation for min–max 3-BGP and a 5/3-approximation for max–min 3-BGP, respectively. These are the first non-trivial approximation algorithms for 3-BGP, to our best knowledge. More... »
PAGES1-21
http://scigraph.springernature.com/pub.10.1007/s10878-020-00544-w
DOIhttp://dx.doi.org/10.1007/s10878-020-00544-w
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1124916632
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/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Pure Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Applied Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Numerical and Computational Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Mathematics, Taizhou University, Linhai, China",
"id": "http://www.grid.ac/institutes/grid.440657.4",
"name": [
"Department of Mathematics, Taizhou University, Linhai, China"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Guangting",
"id": "sg:person.015270460302.04",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015270460302.04"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China",
"id": "http://www.grid.ac/institutes/grid.411963.8",
"name": [
"Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Yong",
"id": "sg:person.010555136403.19",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555136403.19"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Division of Information System Design, Tokyo Denki University, Saitama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Division of Information System Design, Tokyo Denki University, Saitama, Japan"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Zhi-Zhong",
"id": "sg:person.015654265661.98",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computing Science, University of Alberta, Edmonton, Canada",
"id": "http://www.grid.ac/institutes/grid.17089.37",
"name": [
"Department of Computing Science, University of Alberta, Edmonton, Canada"
],
"type": "Organization"
},
"familyName": "Lin",
"givenName": "Guohui",
"id": "sg:person.01130357621.02",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "School of EECS, Peking University, Beijing, China",
"id": "http://www.grid.ac/institutes/grid.11135.37",
"name": [
"School of EECS, Peking University, Beijing, China"
],
"type": "Organization"
},
"familyName": "Liu",
"givenName": "Tian",
"id": "sg:person.011657527023.31",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011657527023.31"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China",
"id": "http://www.grid.ac/institutes/grid.411963.8",
"name": [
"Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China"
],
"type": "Organization"
},
"familyName": "Zhang",
"givenName": "An",
"id": "sg:person.015273653637.29",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015273653637.29"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-319-78455-7_3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1101647685",
"https://doi.org/10.1007/978-3-319-78455-7_3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-24983-9_19",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035221403",
"https://doi.org/10.1007/978-3-642-24983-9_19"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10898-012-0028-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011271850",
"https://doi.org/10.1007/s10898-012-0028-8"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01896190",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050830116",
"https://doi.org/10.1007/bf01896190"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-030-36412-0_11",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1123159174",
"https://doi.org/10.1007/978-3-030-36412-0_11"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-62127-2_4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1090338611",
"https://doi.org/10.1007/978-3-319-62127-2_4"
],
"type": "CreativeWork"
}
],
"datePublished": "2020-02-17",
"datePublishedReg": "2020-02-17",
"description": "Given a vertex-weighted connected graph G=(V,E,w(\u00b7))\\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}$$G = (V, E, w(\\cdot ))$$\\end{document}, the maximally balanced connected graphk-partition (k-BGP) seeks to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected and the weights of these k parts are as balanced as possible. When the concrete objective is to maximize the minimum (to minimize the maximum, respectively) weight of the k parts, the problem is denoted as max\u2013mink-BGP (min\u2013maxk-BGP, respectively), and has received much study since about four decades ago. On general graphs, max\u2013mink-BGP is strongly NP-hard for every fixed k\u22652\\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}$$k \\ge 2$$\\end{document}, and remains NP-hard even for the vertex uniformly weighted case; when k is part of the input, the problem is denoted as max\u2013min BGP, and cannot be approximated within 6/5 unless P =\\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}$$=$$\\end{document} NP. In this paper, we study the tripartition problems from approximation algorithms perspective and present a 3/2-approximation for min\u2013max 3-BGP and a 5/3-approximation for max\u2013min 3-BGP, respectively. These are the first non-trivial approximation algorithms for 3-BGP, to our best knowledge.",
"genre": "article",
"id": "sg:pub.10.1007/s10878-020-00544-w",
"inLanguage": "en",
"isAccessibleForFree": false,
"isFundedItemOf": [
{
"id": "sg:grant.8898306",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.8124106",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.7538013",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.8132243",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1036683",
"issn": [
"1382-6905",
"1573-2886"
],
"name": "Journal of Combinatorial Optimization",
"publisher": "Springer Nature",
"type": "Periodical"
}
],
"keywords": [
"approximation algorithm",
"k parts",
"general graphs",
"max-min",
"non-trivial approximation",
"min-max",
"BGP",
"first non-trivial approximation",
"algorithm",
"graph",
"NPs",
"connected graph",
"concrete objectives",
"non-empty parts",
"minimum weight",
"subgraphs",
"vertices",
"problem",
"input",
"approximation",
"good knowledge",
"part",
"knowledge",
"objective",
"decades",
"weight",
"cases",
"study",
"paper"
],
"name": "Approximation algorithms for the maximally balanced connected graph tripartition problem",
"pagination": "1-21",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1124916632"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10878-020-00544-w"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10878-020-00544-w",
"https://app.dimensions.ai/details/publication/pub.1124916632"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:38",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_865.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s10878-020-00544-w"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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/s10878-020-00544-w'
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/s10878-020-00544-w'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-020-00544-w'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10878-020-00544-w'
This table displays all metadata directly associated to this object as RDF triples.
168 TRIPLES
22 PREDICATES
60 URIs
44 LITERALS
4 BLANK NODES