An O (log2 k )-Competitive Algorithm for Metric Bipartite Matching

No abstract is available for this paper.

• Publication year

  2007

• Venue

  Embedded Systems and Applications

• Publication date

  2007-10-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-540-75520-3_47
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Online Transportation Problem: On the Exponential Boost of One Extra Server

  2008cited by this paper
• Randomized online algorithms for minimum metric bipartite matching

  2006influential reference
• AdWords and generalized on-line matching

  2005cited by this paper
• The Online Matching Problem on a Line

  2003cited by this paper
• Online Matching On a Line

  2003influential reference
• A tight bound on approximating arbitrary metrics by tree metrics

  2003cited by this paper
• Combinatorial optimization. Polyhedra and efficiency.

  2003cited by this paper
• Developments from a June 1996 seminar on Online algorithms: the state of the art

  1998cited by this paper
• On approximating arbitrary metrices by tree metrics

  1998cited by this paper
• Combinatorial optimization

  1997cited by this paper
• On-line Network Optimization Problems

  1996cited by this paper
• Probabilistic approximation of metric spaces and its algorithmic applications

  1996cited by this paper
• An optimal deterministic algorithm for online b-matching

  1996cited by this paper
• The Online Transportation Problem

  1995cited by this paper
• On the k-server conjecture

  1995cited by this paper
• Online Weighted Matching

  1993influential reference
• Searching in the Plane

  1993cited by this paper
• A general approximation technique for constrained forest problems

  1992cited by this paper
• On-Line Algorithms for Weighted Bipartite Matching and Stable Marriages

  1991cited by this paper
• An optimal algorithm for on-line bipartite matching

  1990cited by this paper
• Competitive algorithms for on-line problems

  1988cited by this paper
• Heuristic Matching for Graphs Satisfying the Triangle Inequality

  1984cited by this paper
• The Travelling Salesman Problem and Minimum Matching in the Unit Square

  1983cited by this paper
• On a Greedy Heuristic for Complete Matching

  1981cited by this paper

• Competitive Online Transportation Simplified

  2025cites this paper
• A Nearly Optimal Deterministic Algorithm for Online Transportation Problem

  2024cites this paper
• An $O(\log n)$-Competitive Posted-Price Algorithm for Online Matching on the Line

  2023cites this paper
• Deterministic Primal-Dual Algorithms for Online k-way Matching with Delays

  2023cites this paper
• Competitive Analysis of Online Facility Assignment for General Layout of Servers on a Line

  2023cites this paper
• Resource Augmentation Analysis of the Greedy Algorithm for the Online Transportation Problem

  2023cites this paper
• Solving the Online Assignment Problem with Machine Learned Advice

  2022influential citation
• Capacity-Insensitive Algorithms for Online Facility Assignment Problems on a Line

  2022cites this paper
• The Power of Greedy for Online Minimum Cost Matching on the Line

  2022cites this paper
• HST+: An Efficient Index for Embedding Arbitrary Metric Spaces

  2021cites this paper
• Matching Theory Under Uncertainty

  2021cites this paper
• The Value of Excess Supply in Spatial Matching Markets

  2021cites this paper
• Dynamic Stochastic Matching Under Limited Time

  2020cites this paper
• Matching Drivers to Riders: A Two-Stage Robust Approach

  2020cites this paper
• Competitive Analysis for Two Variants of Online Metric Matching Problem

  2020cites this paper
• Warranty Matching in a Consumer Electronics Closed-Loop Supply Chain

  2020influential citation
• Minimizing Maximum Delay of Task Assignment in Spatial Crowdsourcing

  2019cites this paper
• Stochastic Online Metric Matching

  2019cites this paper
• An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals

  2019cites this paper
• PERMUTATION Strikes Back: The Power of Recourse in Online Metric Matching

  2019cites this paper
• Online Facility Assignment

  2018cites this paper
• DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals

  2018cites this paper
• DISPATCH: An Optimal Algorithm for Online Perfect Bipartite Matching with i.i.d. Arrivals

  2018cites this paper
• An Input Sensitive Online Algorithm for the Metric Bipartite Matching Problem

  2017cites this paper
• Input Sensitive Analysis of a Minimum Metric Bipartite Matching Algorithm

  2017cites this paper
• Online algorithms for facility assignment problem

  2016cites this paper
• Online Minimum Matching in Real-Time Spatial Data: Experiments and Analysis

  2016cites this paper
• Online matching: haste makes waste!

  2016cites this paper
• A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching

  2016cites this paper
• Reverse logistics for consumer electronics : forecasting failures, managing inventory, and matching warranties

  2015cites this paper
• Near-Optimal Deterministic Steiner Tree Maintenance in Sensor Networks

  2014cites this paper
• Competitive strategies for an online generalized assignment problem with a service consecution constraint

  2013cites this paper
• The Online Metric Matching Problem for Doubling Metrics

  2012cites this paper
• Improved Bounds for Online Preemptive Matching

  2012cites this paper
• Energy-Efficient Online Scheduling with Deadlines

  2010cites this paper
• Distributed resource management and matching in sensor networks

  2009influential citation
• Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model

  2009cites this paper
• SIGACT news online algorithms column 13: 2007 - an offine perspective

  2008cites this paper