Biobjective Online Bipartite Matching View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Gagan Aggarwal , Yang Cai , Aranyak Mehta , George Pierrakos

ABSTRACT

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 – thus enabling the necessary skipping of vertices – and simultaneously runs the color-oblivious algorithm Ranking. We prove that this algorithm achieves a competitive ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \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 − 1/e ≃ 0.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. More... »

PAGES

218-231

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-13129-0_16

DOI

http://dx.doi.org/10.1007/978-3-319-13129-0_16

DIMENSIONS

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


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": "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

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/978-3-319-13129-0_16'

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/978-3-319-13129-0_16'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-13129-0_16'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-13129-0_16'


 

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

165 TRIPLES      23 PREDICATES      95 URIs      88 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-13129-0_16 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nad18e839c68e4dd890e041fc8d4c7462
4 schema:datePublished 2014
5 schema:datePublishedReg 2014-01-01
6 schema: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 – thus enabling the necessary skipping of vertices – and simultaneously runs the color-oblivious algorithm Ranking. We prove that this algorithm achieves a competitive ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \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 − 1/e ≃ 0.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.
7 schema:editor N2c66459c234a430eb8aa3888e12e92ed
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Naf60435dc6cc4ad6a88c1023b44ac6f9
12 schema:keywords Greedy
13 Online Bipartite Matching
14 ad allocation
15 algorithm
16 algorithm rankings
17 allocation
18 applicability
19 biobjective problem
20 bipartite matching
21 blue
22 certain metrics
23 color
24 competitive ratio
25 considerable interest
26 departure
27 deterministic algorithm
28 difficulties
29 edge
30 fact
31 generalization
32 goal
33 graph
34 greedy algorithm
35 hits
36 incoming vertices
37 interest
38 large number
39 locality properties
40 main results
41 manner
42 matching
43 metrics
44 minimum number
45 misses
46 motivation
47 multiple objectives
48 non-trivial ratio
49 number
50 objective
51 online ad allocation
52 online matching
53 particular manner
54 perfect matching
55 practice
56 previous problems
57 previous settings
58 problem
59 properties
60 quality
61 randomized algorithm
62 ranking
63 ratio
64 reasonable algorithm
65 red
66 red edge
67 restriction
68 results
69 revenue
70 same ratio
71 setting
72 simple algorithm
73 single matching
74 skipping
75 standard setting
76 strict generalization
77 technical difficulties
78 technique
79 vertices
80 way
81 schema:name Biobjective Online Bipartite Matching
82 schema:pagination 218-231
83 schema:productId N1a163bc6aae14f89b7b9c3f6296f8d5e
84 N5e35a1ad07f64aad82c919968c155b86
85 schema:publisher Nf0606101cbb5484da579c4314576488d
86 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012789361
87 https://doi.org/10.1007/978-3-319-13129-0_16
88 schema:sdDatePublished 2022-05-20T07:48
89 schema:sdLicense https://scigraph.springernature.com/explorer/license/
90 schema:sdPublisher Nca232a26629141bf925173e8fd57707b
91 schema:url https://doi.org/10.1007/978-3-319-13129-0_16
92 sgo:license sg:explorer/license/
93 sgo:sdDataset chapters
94 rdf:type schema:Chapter
95 N1a163bc6aae14f89b7b9c3f6296f8d5e schema:name dimensions_id
96 schema:value pub.1012789361
97 rdf:type schema:PropertyValue
98 N20ef8bdb2ac744cf9be8e50fa43fc715 rdf:first N339c361f37334bbcac43dddd142162b1
99 rdf:rest N2ea2747f0e3840bea58f09eaf4e6b876
100 N2c66459c234a430eb8aa3888e12e92ed rdf:first Nf3644e2675e041cfa19bebb5c7aadf9c
101 rdf:rest Nf86c92f1cff0440d8a1635673ab4382d
102 N2ea2747f0e3840bea58f09eaf4e6b876 rdf:first sg:person.010106546671.08
103 rdf:rest N3fc7e1693dee4e2582732a855e9cdfdc
104 N339c361f37334bbcac43dddd142162b1 schema:affiliation grid-institutes:grid.14709.3b
105 schema:familyName Cai
106 schema:givenName Yang
107 rdf:type schema:Person
108 N3fc7e1693dee4e2582732a855e9cdfdc rdf:first sg:person.010704127271.62
109 rdf:rest rdf:nil
110 N5e35a1ad07f64aad82c919968c155b86 schema:name doi
111 schema:value 10.1007/978-3-319-13129-0_16
112 rdf:type schema:PropertyValue
113 N8d471631432d4994b0ee65fdfbea23a4 schema:familyName Qi
114 schema:givenName Qi
115 rdf:type schema:Person
116 Nad18e839c68e4dd890e041fc8d4c7462 rdf:first sg:person.012226466501.57
117 rdf:rest N20ef8bdb2ac744cf9be8e50fa43fc715
118 Naf60435dc6cc4ad6a88c1023b44ac6f9 schema:isbn 978-3-319-13128-3
119 978-3-319-13129-0
120 schema:name Web and Internet Economics
121 rdf:type schema:Book
122 Nca232a26629141bf925173e8fd57707b schema:name Springer Nature - SN SciGraph project
123 rdf:type schema:Organization
124 Nd350a00f90094cd9bc5913eb9e35bbf4 schema:familyName Ye
125 schema:givenName Yinyu
126 rdf:type schema:Person
127 Ned71cd5be54a45bb8b6c801d7a644d22 rdf:first Nd350a00f90094cd9bc5913eb9e35bbf4
128 rdf:rest rdf:nil
129 Nf0606101cbb5484da579c4314576488d schema:name Springer Nature
130 rdf:type schema:Organisation
131 Nf3644e2675e041cfa19bebb5c7aadf9c schema:familyName Liu
132 schema:givenName Tie-Yan
133 rdf:type schema:Person
134 Nf86c92f1cff0440d8a1635673ab4382d rdf:first N8d471631432d4994b0ee65fdfbea23a4
135 rdf:rest Ned71cd5be54a45bb8b6c801d7a644d22
136 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
137 schema:name Information and Computing Sciences
138 rdf:type schema:DefinedTerm
139 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
140 schema:name Artificial Intelligence and Image Processing
141 rdf:type schema:DefinedTerm
142 sg:person.010106546671.08 schema:affiliation grid-institutes:grid.420451.6
143 schema:familyName Mehta
144 schema:givenName Aranyak
145 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08
146 rdf:type schema:Person
147 sg:person.010704127271.62 schema:affiliation grid-institutes:grid.47840.3f
148 schema:familyName Pierrakos
149 schema:givenName George
150 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010704127271.62
151 rdf:type schema:Person
152 sg:person.012226466501.57 schema:affiliation grid-institutes:grid.420451.6
153 schema:familyName Aggarwal
154 schema:givenName Gagan
155 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012226466501.57
156 rdf:type schema:Person
157 grid-institutes:grid.14709.3b schema:alternateName McGill University, Montreal, QC, Canada
158 schema:name McGill University, Montreal, QC, Canada
159 rdf:type schema:Organization
160 grid-institutes:grid.420451.6 schema:alternateName Google Research, Mountain View, CA, USA
161 schema:name Google Research, Mountain View, CA, USA
162 rdf:type schema:Organization
163 grid-institutes:grid.47840.3f schema:alternateName UC Berkeley, Berkeley, CA, USA
164 schema:name UC Berkeley, Berkeley, CA, USA
165 rdf:type schema:Organization
 




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


...