On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2020-06-05

AUTHORS

Tanima Chatterjee, Bhaskar DasGupta, Laura Palmieri, Zainab Al-Qurashi, Anastasios Sidiropoulos

ABSTRACT

Partisan gerrymandering is a major cause for voter disenfranchisement in United States. However, convincing US courts to adopt specific measures to quantify gerrymandering has been of limited success to date. Recently, Stephanopoulos and McGhee in several papers introduced a new measure of partisan gerrymandering via the so-called “efficiency gap” that computes the absolute difference of wasted votes between two political parties in a two-party system; from a legal point of view the measure was found legally convincing in a US appeals court in a case that claims that the legislative map of the state of Wisconsin was gerrymandered. The goal of this article is to formalize and provide theoretical and empirical algorithmic analyses of the computational problem of minimizing this measure. To this effect, we show the following: (a) On the theoretical side, we formalize the corresponding minimization problem and provide non-trivial mathematical and computational complexity properties of the problem of minimizing the efficiency gap measure. Specifically, we prove the following results for the formalized minimization problem: (i) We show that the efficiency gap measure attains only a finite discrete set of rational values. (observations of similar nature but using different arguments were also made independently by Cho and Wendy (Univ Pa Law Rev 166(1), Article 2, 2017). (ii) We show that, assuming P ≠NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ne \textsf {NP}$$\end{document}, for general maps and arbitrary numeric electoral data the minimization problem does not admit any polynomial time algorithm with finite approximation ratio. Moreover, we show that the problem still remains NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf {NP}$$\end{document}-complete even if the numeric electoral data is linear in the number of districts, provided the map is provided in the form of a planar graph (or, equivalently, a polygonal subdivision of the two-dimensional Euclidean plane). (iii) Notwithstanding the previous hardness results, we show that efficient exact or efficient approximation algorithms can be designed if one assumes some reasonable restrictions on the map and electoral data. Items (ii) and (iii) mentioned above are the first non-trivial computational complexity and algorithmic analyses of this measure of gerrymandering. (b) On the empirical side, we provide a simple and fast algorithm that can “un-gerrymander” the district maps for the states of Texas, Virginia, Wisconsin and Pennsylvania (based on the efficiency gap measure) by bring their efficiency gaps to acceptable levels from the current unacceptable levels. To the best of our knowledge, ours is the first publicly available implementation and its corresponding evaluation on real data for any algorithm for the efficiency gap measure. Our work thus shows that, notwithstanding the general worst-case approximation hardness of the efficiency gap measure as shown by us, finding district maps with acceptable levels of efficiency gaps could be a computationally tractable problem from a practical point of view. Based on these empirical results, we also provide some interesting insights into three practical issues related the efficiency gap measure. More... »

PAGES

512-546

References to SciGraph publications

  • 1995. Structural Complexity I in NONE
  • 1972. Reducibility among Combinatorial Problems in COMPLEXITY OF COMPUTER COMPUTATIONS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10878-020-00589-x

    DOI

    http://dx.doi.org/10.1007/s10878-020-00589-x

    DIMENSIONS

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


    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"
          }, 
          {
            "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 Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA", 
              "id": "http://www.grid.ac/institutes/grid.185648.6", 
              "name": [
                "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chatterjee", 
            "givenName": "Tanima", 
            "id": "sg:person.07403364123.71", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07403364123.71"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA", 
              "id": "http://www.grid.ac/institutes/grid.185648.6", 
              "name": [
                "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "DasGupta", 
            "givenName": "Bhaskar", 
            "id": "sg:person.0763403270.10", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA", 
              "id": "http://www.grid.ac/institutes/grid.185648.6", 
              "name": [
                "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Palmieri", 
            "givenName": "Laura", 
            "id": "sg:person.015444551605.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015444551605.19"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA", 
              "id": "http://www.grid.ac/institutes/grid.185648.6", 
              "name": [
                "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Al-Qurashi", 
            "givenName": "Zainab", 
            "id": "sg:person.014017061201.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014017061201.70"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA", 
              "id": "http://www.grid.ac/institutes/grid.185648.6", 
              "name": [
                "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sidiropoulos", 
            "givenName": "Anastasios", 
            "id": "sg:person.0745563556.15", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0745563556.15"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-79235-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049414081", 
              "https://doi.org/10.1007/978-3-642-79235-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4684-2001-2_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007977430", 
              "https://doi.org/10.1007/978-1-4684-2001-2_9"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2020-06-05", 
        "datePublishedReg": "2020-06-05", 
        "description": "Partisan gerrymandering is a major cause for voter disenfranchisement in United States. However, convincing US courts to adopt specific measures to quantify gerrymandering has been of limited success to date. Recently, Stephanopoulos and McGhee in several papers introduced a new measure of partisan gerrymandering via the so-called \u201cefficiency gap\u201d that computes the absolute difference of wasted votes between two political parties in a two-party system; from a legal point of view the measure was found legally convincing in a US appeals court in a case that claims that the legislative map of the state of Wisconsin was gerrymandered. The goal of this article is to formalize and provide theoretical and empirical algorithmic analyses of the computational problem of minimizing this measure. To this effect, we show the following: (a) On the theoretical side, we formalize the corresponding minimization problem and provide non-trivial mathematical and computational complexity properties of the problem of minimizing the efficiency gap measure. Specifically, we prove the following results for the formalized minimization problem: (i) We show that the efficiency gap measure attains only a finite discrete set of rational values. (observations of similar nature but using different arguments were also made independently by Cho and Wendy (Univ Pa Law Rev 166(1), Article 2, 2017). (ii) We show that, assuming P\u00a0\u2260NP\\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}$$\\ne \\textsf {NP}$$\\end{document}, for general maps and arbitrary numeric electoral data the minimization problem does not admit any polynomial time algorithm with finite approximation ratio. Moreover, we show that the problem still remains NP\\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}$$\\textsf {NP}$$\\end{document}-complete even if the numeric electoral data is linear in the number of districts, provided the map is provided in the form of a planar graph (or, equivalently, a polygonal subdivision of the two-dimensional Euclidean plane). (iii) Notwithstanding the previous hardness results, we show that efficient exact or efficient approximation algorithms can be designed if one assumes some reasonable restrictions on the map and electoral data. Items (ii) and (iii) mentioned above are the first non-trivial computational complexity and algorithmic analyses of this measure of gerrymandering. (b) On the empirical side, we provide a simple and fast algorithm that can \u201cun-gerrymander\u201d the district maps for the states of Texas, Virginia, Wisconsin and Pennsylvania (based on the efficiency gap measure) by bring their efficiency gaps to acceptable levels from the current unacceptable levels. To the best of our knowledge, ours is the first publicly available implementation and its corresponding evaluation on real data for any algorithm for the efficiency gap measure. Our work thus shows that, notwithstanding the general worst-case approximation hardness of the efficiency gap measure as shown by us, finding district maps with acceptable levels of efficiency gaps could be a computationally tractable problem from a practical point of view. Based on these empirical results, we also provide some interesting insights into three practical issues related the efficiency gap measure.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10878-020-00589-x", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.3580864", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.7704338", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.3135580", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.7070479", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.8566396", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.3934301", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1036683", 
            "issn": [
              "1382-6905", 
              "1573-2886"
            ], 
            "name": "Journal of Combinatorial Optimization", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "40"
          }
        ], 
        "keywords": [
          "partisan gerrymandering", 
          "gap measures", 
          "computational complexity properties", 
          "US courts", 
          "appeals court", 
          "legal point", 
          "voter disenfranchisement", 
          "two-party system", 
          "gerrymandering", 
          "state of Wisconsin", 
          "Court", 
          "finite discrete set", 
          "political parties", 
          "United States", 
          "specific measures", 
          "corresponding minimization problem", 
          "algorithmic analysis", 
          "parties", 
          "disenfranchisement", 
          "Stephanopoulos", 
          "state", 
          "vote", 
          "new measure", 
          "article", 
          "limited success", 
          "measures", 
          "McGhee", 
          "problem", 
          "view", 
          "cases", 
          "goal", 
          "gap", 
          "complexity properties", 
          "Wisconsin", 
          "point", 
          "system", 
          "efficiency gap", 
          "theoretical side", 
          "success", 
          "paper", 
          "date", 
          "side", 
          "discrete set", 
          "cause", 
          "analysis", 
          "set", 
          "values", 
          "properties", 
          "rational values", 
          "differences", 
          "effect", 
          "results", 
          "minimization problem", 
          "major cause", 
          "computational problems", 
          "maps", 
          "absolute difference"
        ], 
        "name": "On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering", 
        "pagination": "512-546", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1128245097"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10878-020-00589-x"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10878-020-00589-x", 
          "https://app.dimensions.ai/details/publication/pub.1128245097"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:37", 
        "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_832.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10878-020-00589-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/s10878-020-00589-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/s10878-020-00589-x'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-020-00589-x'

    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-00589-x'


     

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

    171 TRIPLES      22 PREDICATES      85 URIs      73 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10878-020-00589-x schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 anzsrc-for:0102
    4 anzsrc-for:0103
    5 schema:author N836becc4748948e89d22549ab0783ef4
    6 schema:citation sg:pub.10.1007/978-1-4684-2001-2_9
    7 sg:pub.10.1007/978-3-642-79235-9
    8 schema:datePublished 2020-06-05
    9 schema:datePublishedReg 2020-06-05
    10 schema:description Partisan gerrymandering is a major cause for voter disenfranchisement in United States. However, convincing US courts to adopt specific measures to quantify gerrymandering has been of limited success to date. Recently, Stephanopoulos and McGhee in several papers introduced a new measure of partisan gerrymandering via the so-called “efficiency gap” that computes the absolute difference of wasted votes between two political parties in a two-party system; from a legal point of view the measure was found legally convincing in a US appeals court in a case that claims that the legislative map of the state of Wisconsin was gerrymandered. The goal of this article is to formalize and provide theoretical and empirical algorithmic analyses of the computational problem of minimizing this measure. To this effect, we show the following: (a) On the theoretical side, we formalize the corresponding minimization problem and provide non-trivial mathematical and computational complexity properties of the problem of minimizing the efficiency gap measure. Specifically, we prove the following results for the formalized minimization problem: (i) We show that the efficiency gap measure attains only a finite discrete set of rational values. (observations of similar nature but using different arguments were also made independently by Cho and Wendy (Univ Pa Law Rev 166(1), Article 2, 2017). (ii) We show that, assuming P ≠NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ne \textsf {NP}$$\end{document}, for general maps and arbitrary numeric electoral data the minimization problem does not admit any polynomial time algorithm with finite approximation ratio. Moreover, we show that the problem still remains NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf {NP}$$\end{document}-complete even if the numeric electoral data is linear in the number of districts, provided the map is provided in the form of a planar graph (or, equivalently, a polygonal subdivision of the two-dimensional Euclidean plane). (iii) Notwithstanding the previous hardness results, we show that efficient exact or efficient approximation algorithms can be designed if one assumes some reasonable restrictions on the map and electoral data. Items (ii) and (iii) mentioned above are the first non-trivial computational complexity and algorithmic analyses of this measure of gerrymandering. (b) On the empirical side, we provide a simple and fast algorithm that can “un-gerrymander” the district maps for the states of Texas, Virginia, Wisconsin and Pennsylvania (based on the efficiency gap measure) by bring their efficiency gaps to acceptable levels from the current unacceptable levels. To the best of our knowledge, ours is the first publicly available implementation and its corresponding evaluation on real data for any algorithm for the efficiency gap measure. Our work thus shows that, notwithstanding the general worst-case approximation hardness of the efficiency gap measure as shown by us, finding district maps with acceptable levels of efficiency gaps could be a computationally tractable problem from a practical point of view. Based on these empirical results, we also provide some interesting insights into three practical issues related the efficiency gap measure.
    11 schema:genre article
    12 schema:inLanguage en
    13 schema:isAccessibleForFree true
    14 schema:isPartOf N1ff78c8789da42d29344633634ff23c2
    15 Ne04e151376d44ce196571092b5c15c3f
    16 sg:journal.1036683
    17 schema:keywords Court
    18 McGhee
    19 Stephanopoulos
    20 US courts
    21 United States
    22 Wisconsin
    23 absolute difference
    24 algorithmic analysis
    25 analysis
    26 appeals court
    27 article
    28 cases
    29 cause
    30 complexity properties
    31 computational complexity properties
    32 computational problems
    33 corresponding minimization problem
    34 date
    35 differences
    36 discrete set
    37 disenfranchisement
    38 effect
    39 efficiency gap
    40 finite discrete set
    41 gap
    42 gap measures
    43 gerrymandering
    44 goal
    45 legal point
    46 limited success
    47 major cause
    48 maps
    49 measures
    50 minimization problem
    51 new measure
    52 paper
    53 parties
    54 partisan gerrymandering
    55 point
    56 political parties
    57 problem
    58 properties
    59 rational values
    60 results
    61 set
    62 side
    63 specific measures
    64 state
    65 state of Wisconsin
    66 success
    67 system
    68 theoretical side
    69 two-party system
    70 values
    71 view
    72 vote
    73 voter disenfranchisement
    74 schema:name On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering
    75 schema:pagination 512-546
    76 schema:productId Nc0fb51f331ea43949feaf556f29e2824
    77 Ndca674247d5b4b70bffc70ce5205b107
    78 schema:sameAs https://app.dimensions.ai/details/publication/pub.1128245097
    79 https://doi.org/10.1007/s10878-020-00589-x
    80 schema:sdDatePublished 2022-05-20T07:37
    81 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    82 schema:sdPublisher N26c38d59e03c44fea203b70e9503248d
    83 schema:url https://doi.org/10.1007/s10878-020-00589-x
    84 sgo:license sg:explorer/license/
    85 sgo:sdDataset articles
    86 rdf:type schema:ScholarlyArticle
    87 N1ff78c8789da42d29344633634ff23c2 schema:volumeNumber 40
    88 rdf:type schema:PublicationVolume
    89 N26c38d59e03c44fea203b70e9503248d schema:name Springer Nature - SN SciGraph project
    90 rdf:type schema:Organization
    91 N54f5dfe1110e44aca0f2b3ff77c86082 rdf:first sg:person.015444551605.19
    92 rdf:rest Nb573c6dfaf59410a952511ee11c1e021
    93 N75540c950e9c430aa8dd7f3a60177fc0 rdf:first sg:person.0763403270.10
    94 rdf:rest N54f5dfe1110e44aca0f2b3ff77c86082
    95 N836becc4748948e89d22549ab0783ef4 rdf:first sg:person.07403364123.71
    96 rdf:rest N75540c950e9c430aa8dd7f3a60177fc0
    97 Nb573c6dfaf59410a952511ee11c1e021 rdf:first sg:person.014017061201.70
    98 rdf:rest Nd4beec5bf5174cffa857a00ff78f2e39
    99 Nc0fb51f331ea43949feaf556f29e2824 schema:name dimensions_id
    100 schema:value pub.1128245097
    101 rdf:type schema:PropertyValue
    102 Nd4beec5bf5174cffa857a00ff78f2e39 rdf:first sg:person.0745563556.15
    103 rdf:rest rdf:nil
    104 Ndca674247d5b4b70bffc70ce5205b107 schema:name doi
    105 schema:value 10.1007/s10878-020-00589-x
    106 rdf:type schema:PropertyValue
    107 Ne04e151376d44ce196571092b5c15c3f schema:issueNumber 2
    108 rdf:type schema:PublicationIssue
    109 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    110 schema:name Mathematical Sciences
    111 rdf:type schema:DefinedTerm
    112 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    113 schema:name Pure Mathematics
    114 rdf:type schema:DefinedTerm
    115 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    116 schema:name Applied Mathematics
    117 rdf:type schema:DefinedTerm
    118 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    119 schema:name Numerical and Computational Mathematics
    120 rdf:type schema:DefinedTerm
    121 sg:grant.3135580 http://pending.schema.org/fundedItem sg:pub.10.1007/s10878-020-00589-x
    122 rdf:type schema:MonetaryGrant
    123 sg:grant.3580864 http://pending.schema.org/fundedItem sg:pub.10.1007/s10878-020-00589-x
    124 rdf:type schema:MonetaryGrant
    125 sg:grant.3934301 http://pending.schema.org/fundedItem sg:pub.10.1007/s10878-020-00589-x
    126 rdf:type schema:MonetaryGrant
    127 sg:grant.7070479 http://pending.schema.org/fundedItem sg:pub.10.1007/s10878-020-00589-x
    128 rdf:type schema:MonetaryGrant
    129 sg:grant.7704338 http://pending.schema.org/fundedItem sg:pub.10.1007/s10878-020-00589-x
    130 rdf:type schema:MonetaryGrant
    131 sg:grant.8566396 http://pending.schema.org/fundedItem sg:pub.10.1007/s10878-020-00589-x
    132 rdf:type schema:MonetaryGrant
    133 sg:journal.1036683 schema:issn 1382-6905
    134 1573-2886
    135 schema:name Journal of Combinatorial Optimization
    136 schema:publisher Springer Nature
    137 rdf:type schema:Periodical
    138 sg:person.014017061201.70 schema:affiliation grid-institutes:grid.185648.6
    139 schema:familyName Al-Qurashi
    140 schema:givenName Zainab
    141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014017061201.70
    142 rdf:type schema:Person
    143 sg:person.015444551605.19 schema:affiliation grid-institutes:grid.185648.6
    144 schema:familyName Palmieri
    145 schema:givenName Laura
    146 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015444551605.19
    147 rdf:type schema:Person
    148 sg:person.07403364123.71 schema:affiliation grid-institutes:grid.185648.6
    149 schema:familyName Chatterjee
    150 schema:givenName Tanima
    151 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07403364123.71
    152 rdf:type schema:Person
    153 sg:person.0745563556.15 schema:affiliation grid-institutes:grid.185648.6
    154 schema:familyName Sidiropoulos
    155 schema:givenName Anastasios
    156 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0745563556.15
    157 rdf:type schema:Person
    158 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.185648.6
    159 schema:familyName DasGupta
    160 schema:givenName Bhaskar
    161 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
    162 rdf:type schema:Person
    163 sg:pub.10.1007/978-1-4684-2001-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007977430
    164 https://doi.org/10.1007/978-1-4684-2001-2_9
    165 rdf:type schema:CreativeWork
    166 sg:pub.10.1007/978-3-642-79235-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049414081
    167 https://doi.org/10.1007/978-3-642-79235-9
    168 rdf:type schema:CreativeWork
    169 grid-institutes:grid.185648.6 schema:alternateName Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA
    170 schema:name Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA
    171 rdf:type schema:Organization
     




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


    ...