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": "Google Research, Mountain View, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.420451.6", 
          "name": [
            "Google Research, Mountain View, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Aggarwal", 
        "givenName": "Gagan", 
        "id": "sg:person.012226466501.57", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012226466501.57"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "McGill University, Montreal, QC, Canada", 
          "id": "http://www.grid.ac/institutes/grid.14709.3b", 
          "name": [
            "McGill University, Montreal, QC, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cai", 
        "givenName": "Yang", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Google Research, Mountain View, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.420451.6", 
          "name": [
            "Google Research, Mountain View, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehta", 
        "givenName": "Aranyak", 
        "id": "sg:person.010106546671.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UC Berkeley, Berkeley, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "UC Berkeley, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pierrakos", 
        "givenName": "George", 
        "id": "sg:person.010704127271.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010704127271.62"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "Online Matching has been a problem of considerable interest recently, particularly due to its applicability in Online Ad Allocation. In practice, there are usually multiple objectives which need to be simultaneously optimized, e.g., revenue and quality. We capture this motivation by introducing the problem of Biobjective Online Bipartite Matching. This is a strict generalization of the standard setting. In our problem, the graph has edges of two colors, Red and Blue. The goal is to find a single matching that contains a large number of edges of each color.We first show how this problem is a departure from previous settings: In all previous problems, the Greedy algorithm gives a non-trivial ratio, typically 1/2. In the biobjective problem, we show that the competitive ratio of Greedy is 0, and in fact, any reasonable algorithm would have to skip vertices, i.e., not match some incoming vertices even though they have an edge available.As our main result, we introduce an algorithm which randomly discards some edges of the graph in a particular manner \u2013 thus enabling the necessary skipping of vertices \u2013 and simultaneously runs the color-oblivious algorithm Ranking. We prove that this algorithm achieves a competitive ratio of \\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}$3 - 4/\\sqrt{e} \\simeq 0.573$\\end{document} for graphs which have a perfect matching of each color. This beats the upper bound of 1/2 for deterministic algorithms, and comes close to the upper bound of 1\u2009\u2212\u20091/e\u2009\u2243\u20090.63 for randomized algorithms, both of which we prove carry over to the bicriteria setting, even with the perfect matching restriction. The technical difficulty lies in analyzing the expected minimum number of blue and red edges in the matching (rather than the minimum of the two expectations). To achieve this, we introduce a charging technique which has a new locality property, i.e., misses are charged to nearby hits, according to a certain metric.Along the way we develop and analyze simpler algorithms for the problem: a deterministic algorithm which achieves a ratio of 0.343, and a simpler randomized algorithm, which achieves, intriguingly, precisely the same ratio.", 
    "editor": [
      {
        "familyName": "Liu", 
        "givenName": "Tie-Yan", 
        "type": "Person"
      }, 
      {
        "familyName": "Qi", 
        "givenName": "Qi", 
        "type": "Person"
      }, 
      {
        "familyName": "Ye", 
        "givenName": "Yinyu", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-13129-0_16", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-13128-3", 
        "978-3-319-13129-0"
      ], 
      "name": "Web and Internet Economics", 
      "type": "Book"
    }, 
    "keywords": [
      "Online Bipartite Matching", 
      "bipartite matching", 
      "deterministic algorithm", 
      "competitive ratio", 
      "single matching", 
      "online ad allocation", 
      "algorithm rankings", 
      "incoming vertices", 
      "ad allocation", 
      "greedy algorithm", 
      "online matching", 
      "locality properties", 
      "randomized algorithm", 
      "strict generalization", 
      "non-trivial ratio", 
      "algorithm", 
      "certain metrics", 
      "multiple objectives", 
      "biobjective problem", 
      "matching", 
      "previous settings", 
      "graph", 
      "reasonable algorithm", 
      "previous problems", 
      "simple algorithm", 
      "minimum number", 
      "large number", 
      "Greedy", 
      "perfect matching", 
      "vertices", 
      "main results", 
      "metrics", 
      "problem", 
      "edge", 
      "misses", 
      "allocation", 
      "particular manner", 
      "ranking", 
      "generalization", 
      "color", 
      "goal", 
      "applicability", 
      "technique", 
      "number", 
      "standard setting", 
      "way", 
      "quality", 
      "setting", 
      "revenue", 
      "considerable interest", 
      "motivation", 
      "difficulties", 
      "interest", 
      "manner", 
      "technical difficulties", 
      "properties", 
      "objective", 
      "hits", 
      "departure", 
      "results", 
      "fact", 
      "restriction", 
      "same ratio", 
      "ratio", 
      "practice", 
      "skipping", 
      "red edge", 
      "red", 
      "blue"
    ], 
    "name": "Biobjective Online Bipartite Matching", 
    "pagination": "218-231", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1012789361"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-13129-0_16"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-13129-0_16", 
      "https://app.dimensions.ai/details/publication/pub.1012789361"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:48", 
    "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/chapter/chapter_421.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-13129-0_16"
  }
]

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

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

165 TRIPLES      23 PREDICATES      95 URIs      88 LITERALS      7 BLANK NODES