ﻻ يوجد ملخص باللغة العربية
Huang et al.~(STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive online and considers general graphs. They showed that the ranking algorithm by Karp et al.~(STOC 1990) is strictly better than $0.5$-competitive and the problem is strictly harder than the online bipartite matching problem in that no algorithms can be $(1-1/e)$-competitive. This paper pins down two tight competitive ratios of classic algorithms for the fully online matching problem. For the fractional version of the problem, we show that a natural instantiation of the water-filling algorithm is $2-sqrt{2} approx 0.585$-competitive, together with a matching hardness result. Interestingly, our hardness result applies to arbitrary algorithms in the edge-arrival models of the online matching problem, improving the state-of-art $frac{1}{1+ln 2} approx 0.5906$ upper bound. For integral algorithms, we show a tight competitive ratio of $approx 0.567$ for the ranking algorithm on bipartite graphs, matching a hardness result by Huang et al. (STOC 2018).
The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-ca
We introduce and study a general version of the fractional online knapsack problem with multiple knapsacks, heterogeneous constraints on which items can be assigned to which knapsack, and rate-limiting constraints on the assignment of items to knapsa
In multi-capacity ridesharing, multiple requests (e.g., customers, food items, parcels) with different origin and destination pairs travel in one resource. In recent years, online multi-capacity ridesharing services (i.e., where assignments are made
We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of
Online algorithms make decisions based on past inputs. In general, the decision may depend on the entire history of inputs. If many computers run the same online algorithm with the same input stream but are started at different times, they do not nec