English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In the online metric bipartite matching problem, we are given a set $S$ ofserver locations in a metric space. Requests arrive one at a time, and on itsarrival, we need to immediately and irrevocably match it to a server at a costwhich is equal to the distance between these locations. A $\alpha$-competitivealgorithm will assign requests to servers so that the total cost is at most$\alpha$ times the cost of $M_{OPT}$ where $M_{OPT}$ is the minimum costmatching between $S$ and $R$.  We consider this problem in the adversarial model for the case where $S$ and$R$ are points on a line and $|S|=|R|=n$. We improve the analysis of thedeterministic Robust Matching Algorithm (RM-Algorithm, Nayyar and RaghvendraFOCS'17) from $O(\log^2 n)$ to an optimal $\Theta(\log n)$. Previously, only arandomized algorithm under a weaker oblivious adversary achieved a competitiveratio of $O(\log n)$ (Gupta and Lewi, ICALP'12). The well-known Work FunctionAlgorithm (WFA) has a competitive ratio of $O(n)$ and $\Omega(\log n)$ for thisproblem. Therefore, WFA cannot achieve an asymptotically better competitiveratio than the RM-Algorithm.

Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line