Ontology type: schema:Chapter Open Access: True

2014

Gagan Aggarwal , Yang Cai , Aranyak Mehta , George Pierrakos

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... »

218-231

Web and Internet Economics

978-3-319-13128-3

978-3-319-13129-0

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

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

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

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

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 |