---
_id: '11789'
abstract:
- lang: eng
  text: "We study a weighted online bipartite matching problem: G(V 1, V 2, E) is
    a weighted bipartite graph where V 1 is known beforehand and the vertices of V
    2 arrive online. The goal is to match vertices of V 2 as they arrive to vertices
    in V 1, so as to maximize the sum of weights of edges in the matching. If assignments
    to V 1 cannot be changed, no bounded competitive ratio is achievable. We study
    the weighted online matching problem with free disposal, where vertices in V 1
    can be assigned multiple times, but only get credit for the maximum weight edge
    assigned to them over the course of the algorithm. For this problem, the greedy
    algorithm is 0.5-competitive and determining whether a better competitive ratio
    is achievable is a well known open problem.\r\n\r\nWe identify an interesting
    special case where the edge weights are decomposable as the product of two factors,
    one corresponding to each end point of the edge. This is analogous to the well
    studied related machines model in the scheduling literature, although the objective
    functions are different. For this case of decomposable edge weights, we design
    a 0.5664 competitive randomized algorithm in complete bipartite graphs. We show
    that such instances with decomposable weights are non-trivial by establishing
    upper bounds of 0.618 for deterministic and 0.8 for randomized algorithms.\r\n\r\nA
    tight competitive ratio of 1 − 1/e ≈ 0.632 was known previously for both the 0-1
    case as well as the case where edge weights depend on the offline vertices only,
    but for these cases, reassignments cannot change the quality of the solution.
    Beating 0.5 for weighted matching where reassignments are necessary has been a
    significant challenge. We thus give the first online algorithm with competitive
    ratio strictly better than 0.5 for a non-trivial case of weighted matching with
    free disposal."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Moses
  full_name: Charikar, Moses
  last_name: Charikar
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Huy L.
  full_name: Nguyễn, Huy L.
  last_name: Nguyễn
citation:
  ama: 'Charikar M, Henzinger MH, Nguyễn HL. Online bipartite matching with decomposable
    weights. In: <i>22nd Annual European Symposium on Algorithms</i>. Vol 8737. Springer
    Nature; 2014:260-271. doi:<a href="https://doi.org/10.1007/978-3-662-44777-2_22">10.1007/978-3-662-44777-2_22</a>'
  apa: 'Charikar, M., Henzinger, M. H., &#38; Nguyễn, H. L. (2014). Online bipartite
    matching with decomposable weights. In <i>22nd Annual European Symposium on Algorithms</i>
    (Vol. 8737, pp. 260–271). Wroclaw, Poland: Springer Nature. <a href="https://doi.org/10.1007/978-3-662-44777-2_22">https://doi.org/10.1007/978-3-662-44777-2_22</a>'
  chicago: Charikar, Moses, Monika H Henzinger, and Huy L. Nguyễn. “Online Bipartite
    Matching with Decomposable Weights.” In <i>22nd Annual European Symposium on Algorithms</i>,
    8737:260–71. Springer Nature, 2014. <a href="https://doi.org/10.1007/978-3-662-44777-2_22">https://doi.org/10.1007/978-3-662-44777-2_22</a>.
  ieee: M. Charikar, M. H. Henzinger, and H. L. Nguyễn, “Online bipartite matching
    with decomposable weights,” in <i>22nd Annual European Symposium on Algorithms</i>,
    Wroclaw, Poland, 2014, vol. 8737, pp. 260–271.
  ista: 'Charikar M, Henzinger MH, Nguyễn HL. 2014. Online bipartite matching with
    decomposable weights. 22nd Annual European Symposium on Algorithms. ESA: Annual
    European Symposium on Algorithms, LNCS, vol. 8737, 260–271.'
  mla: Charikar, Moses, et al. “Online Bipartite Matching with Decomposable Weights.”
    <i>22nd Annual European Symposium on Algorithms</i>, vol. 8737, Springer Nature,
    2014, pp. 260–71, doi:<a href="https://doi.org/10.1007/978-3-662-44777-2_22">10.1007/978-3-662-44777-2_22</a>.
  short: M. Charikar, M.H. Henzinger, H.L. Nguyễn, in:, 22nd Annual European Symposium
    on Algorithms, Springer Nature, 2014, pp. 260–271.
conference:
  end_date: 2014-09-10
  location: Wroclaw, Poland
  name: 'ESA: Annual European Symposium on Algorithms'
  start_date: 2014-09-08
date_created: 2022-08-11T10:41:47Z
date_published: 2014-09-01T00:00:00Z
date_updated: 2023-02-13T11:16:24Z
day: '01'
doi: 10.1007/978-3-662-44777-2_22
extern: '1'
external_id:
  arxiv:
  - '1409.2139'
intvolume: '      8737'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1409.2139
month: '09'
oa: 1
oa_version: Preprint
page: 260 - 271
publication: 22nd Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - 978-366244776-5
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Online bipartite matching with decomposable weights
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8737
year: '2014'
...