A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2004-07

AUTHORS

Michael Saks*, Alex Samorodnitsky†, Leonid Zosin†

ABSTRACT

Given a directed edge-weighted graph and k source-sink pairs, the Minimum Directed Multicut Problem is to find an edge subset with minimal weight, that separates each source-sink pair. Determining the minimum multicut in directed or undirected graphs is NP-hard. The fractional version of the minimum multicut problem is dual to the maximum multicommodity flow problem. The integrality gap for an instance of this problem is the ratio of the minimum weight multicut to the minimum weight fractional multicut; trivially this gap is always at least 1 and it is easy to show that it is at most k. In the analogous problem for undirected graphs this upper bound was improved to O(log k).In this paper, for each k an explicit family of examples is presented each with k source-sink pairs for which the integrality gap can be made arbitrarily close to k. This shows that for directed graphs, the trivial upper bound of k can not be improved. More... »

PAGES

525-530

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00493-004-0031-x

DOI

http://dx.doi.org/10.1007/s00493-004-0031-x

DIMENSIONS

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


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/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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Rutgers University, 110 Frelinghuysen Road, 08854-8019, Piscataway, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, 110 Frelinghuysen Road, 08854-8019, Piscataway, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks*", 
        "givenName": "Michael", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Computer Science and Engineering, The Hebrew University of Jerusalem, 93708, Jerusalem, Israel", 
          "id": "http://www.grid.ac/institutes/grid.9619.7", 
          "name": [
            "School of Computer Science and Engineering, The Hebrew University of Jerusalem, 93708, Jerusalem, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Samorodnitsky\u2020", 
        "givenName": "Alex", 
        "id": "sg:person.01066630725.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01066630725.20"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "ITG Inc., 44 Farnsworth Str., 02210, Boston, MA, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "ITG Inc., 44 Farnsworth Str., 02210, Boston, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zosin\u2020", 
        "givenName": "Leonid", 
        "type": "Person"
      }
    ], 
    "datePublished": "2004-07", 
    "datePublishedReg": "2004-07-01", 
    "description": "Given a directed edge-weighted graph and k source-sink pairs, the Minimum Directed Multicut Problem is to find an edge subset with minimal weight, that separates each source-sink pair. Determining the minimum multicut in directed or undirected graphs is NP-hard. The fractional version of the minimum multicut problem is dual to the maximum multicommodity flow problem. The integrality gap for an instance of this problem is the ratio of the minimum weight multicut to the minimum weight fractional multicut; trivially this gap is always at least 1 and it is easy to show that it is at most k. In the analogous problem for undirected graphs this upper bound was improved to O(log k).In this paper, for each k an explicit family of examples is presented each with k source-sink pairs for which the integrality gap can be made arbitrarily close to k. This shows that for directed graphs, the trivial upper bound of k can not be improved.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00493-004-0031-x", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "24"
      }
    ], 
    "keywords": [
      "minimum multicut", 
      "integrality gap", 
      "maximum multicommodity flow problem", 
      "source-sink pairs", 
      "undirected graph", 
      "multicommodity flow problem", 
      "edge-weighted graph", 
      "multicut problem", 
      "minimum multicut problem", 
      "flow problem", 
      "fractional version", 
      "explicit family", 
      "edge subset", 
      "analogous problem", 
      "graph", 
      "multicut", 
      "minimal weight", 
      "problem", 
      "pairs", 
      "gap", 
      "NPs", 
      "version", 
      "network", 
      "instances", 
      "subset", 
      "ratio", 
      "family", 
      "weight", 
      "example", 
      "paper"
    ], 
    "name": "A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks", 
    "pagination": "525-530", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017126832"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00493-004-0031-x"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00493-004-0031-x", 
      "https://app.dimensions.ai/details/publication/pub.1017126832"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-09-02T15:50", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_386.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00493-004-0031-x"
  }
]
 

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/s00493-004-0031-x'

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/s00493-004-0031-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-004-0031-x'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-004-0031-x'


 

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

106 TRIPLES      20 PREDICATES      55 URIs      47 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00493-004-0031-x schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Ne9c2650c52ea489cb27da27a02f1f3a2
4 schema:datePublished 2004-07
5 schema:datePublishedReg 2004-07-01
6 schema:description Given a directed edge-weighted graph and k source-sink pairs, the Minimum Directed Multicut Problem is to find an edge subset with minimal weight, that separates each source-sink pair. Determining the minimum multicut in directed or undirected graphs is NP-hard. The fractional version of the minimum multicut problem is dual to the maximum multicommodity flow problem. The integrality gap for an instance of this problem is the ratio of the minimum weight multicut to the minimum weight fractional multicut; trivially this gap is always at least 1 and it is easy to show that it is at most k. In the analogous problem for undirected graphs this upper bound was improved to O(log k).In this paper, for each k an explicit family of examples is presented each with k source-sink pairs for which the integrality gap can be made arbitrarily close to k. This shows that for directed graphs, the trivial upper bound of k can not be improved.
7 schema:genre article
8 schema:isAccessibleForFree false
9 schema:isPartOf N217f3910a0524ec59f3eb2a3c361d62b
10 Nd2d52e0e6cef4d309befc8c5dae088b4
11 sg:journal.1136493
12 schema:keywords NPs
13 analogous problem
14 edge subset
15 edge-weighted graph
16 example
17 explicit family
18 family
19 flow problem
20 fractional version
21 gap
22 graph
23 instances
24 integrality gap
25 maximum multicommodity flow problem
26 minimal weight
27 minimum multicut
28 minimum multicut problem
29 multicommodity flow problem
30 multicut
31 multicut problem
32 network
33 pairs
34 paper
35 problem
36 ratio
37 source-sink pairs
38 subset
39 undirected graph
40 version
41 weight
42 schema:name A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks
43 schema:pagination 525-530
44 schema:productId N895e1097a96d4031a95e389681d0244f
45 N8da714a8586547f5b5a5ce097e3cbbac
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017126832
47 https://doi.org/10.1007/s00493-004-0031-x
48 schema:sdDatePublished 2022-09-02T15:50
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher N9316ce44cd7742a6b16b6cc2d55fea7e
51 schema:url https://doi.org/10.1007/s00493-004-0031-x
52 sgo:license sg:explorer/license/
53 sgo:sdDataset articles
54 rdf:type schema:ScholarlyArticle
55 N217f3910a0524ec59f3eb2a3c361d62b schema:volumeNumber 24
56 rdf:type schema:PublicationVolume
57 N6d4c9421dd994f30b77bc74e8c8be02b schema:affiliation grid-institutes:None
58 schema:familyName Zosin†
59 schema:givenName Leonid
60 rdf:type schema:Person
61 N895e1097a96d4031a95e389681d0244f schema:name dimensions_id
62 schema:value pub.1017126832
63 rdf:type schema:PropertyValue
64 N8da714a8586547f5b5a5ce097e3cbbac schema:name doi
65 schema:value 10.1007/s00493-004-0031-x
66 rdf:type schema:PropertyValue
67 N9316ce44cd7742a6b16b6cc2d55fea7e schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 Na30e282348274e31b44ffb3969c9d3e4 rdf:first N6d4c9421dd994f30b77bc74e8c8be02b
70 rdf:rest rdf:nil
71 Nd2d52e0e6cef4d309befc8c5dae088b4 schema:issueNumber 3
72 rdf:type schema:PublicationIssue
73 Nd42dea3fd6b844738b4cbb5e3a8e4fb3 rdf:first sg:person.01066630725.20
74 rdf:rest Na30e282348274e31b44ffb3969c9d3e4
75 Ne9c2650c52ea489cb27da27a02f1f3a2 rdf:first sg:person.011520224512.05
76 rdf:rest Nd42dea3fd6b844738b4cbb5e3a8e4fb3
77 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
78 schema:name Mathematical Sciences
79 rdf:type schema:DefinedTerm
80 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
81 schema:name Pure Mathematics
82 rdf:type schema:DefinedTerm
83 sg:journal.1136493 schema:issn 0209-9683
84 1439-6912
85 schema:name Combinatorica
86 schema:publisher Springer Nature
87 rdf:type schema:Periodical
88 sg:person.01066630725.20 schema:affiliation grid-institutes:grid.9619.7
89 schema:familyName Samorodnitsky†
90 schema:givenName Alex
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01066630725.20
92 rdf:type schema:Person
93 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
94 schema:familyName Saks*
95 schema:givenName Michael
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
97 rdf:type schema:Person
98 grid-institutes:None schema:alternateName ITG Inc., 44 Farnsworth Str., 02210, Boston, MA, USA
99 schema:name ITG Inc., 44 Farnsworth Str., 02210, Boston, MA, USA
100 rdf:type schema:Organization
101 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, 110 Frelinghuysen Road, 08854-8019, Piscataway, NJ, USA
102 schema:name Department of Mathematics, Rutgers University, 110 Frelinghuysen Road, 08854-8019, Piscataway, NJ, USA
103 rdf:type schema:Organization
104 grid-institutes:grid.9619.7 schema:alternateName School of Computer Science and Engineering, The Hebrew University of Jerusalem, 93708, Jerusalem, Israel
105 schema:name School of Computer Science and Engineering, The Hebrew University of Jerusalem, 93708, Jerusalem, Israel
106 rdf:type schema:Organization
 




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


...