We present a new approach, called a lazy matching, to the problem of on-line matching on bipartite graphs. Imagine that one side of a graph is given and the vertices of the other side are arriving on-line. Originally, incoming vertex is either irrevocably matched to an another element or stays forever unmatched. A lazy algorithm is allowed to match a new vertex to a group of elements (possibly empty) and afterwords, forced against next vertices, may give up parts of the group. The restriction is that all the time each element is in at most one group. We present an optimal lazy algorithm (deterministic) and prove that its competitive ratio equals @math . The lazy approach allows us to break the barrier of @math , which is the best competitive ratio that can be guaranteed by any deterministic algorithm in the classical on-line matching.
Another similar approach was proposed by @cite_5 as . They consider the weighted matching problem where each incoming vertex @math may be assigned to one of its neighbors or left alone. Each vertex @math accepts at most @math vertices from @math with highest-weighted edges. Here roles of servers and tasks are switched. All tasks are given at once and servers are incoming on-line. Each server has to be assigned to at most one task. In the end, each task chooses at most @math servers from all the servers assigned to it -- the ones with the highest-weighted edge. The main difference from the lazy approach is that once a connection between a server and a task is established it cannot be changed till the very end. There is no such restriction in the lazy approach -- a server may drop its task and take a new one during the on-line process.
@cite_5
1578666690
We study an online weighted assignment problem with a set of fixed nodes corresponding to advertisers and online arrival of nodes corresponding to ad impressions. Advertiser a has a contract for n(a) impressions, and each impression has a set of weighted edges to advertisers. The problem is to assign the impressions online so that while each advertiser a gets n(a) impressions, the total weight of edges assigned is maximized. Our insight is that ad impressions allow for free disposal, that is, advertisers are indifferent to, or prefer being assigned more than n(a) impressions without changing the contract terms. This means that the value of an assignment only includes the n(a) highest-weighted items assigned to each node a. With free disposal, we provide an algorithm for this problem that achieves a competitive ratio of 1 ? 1 e against the offline optimum, and show that this is the best possible ratio. We use a primal dual framework to derive our results, applying a novel exponentially-weighted dual update rule. Furthermore, our algorithm can be applied to a general set of assignment problems including the ad words problem as a special case, matching the previously known 1 ? 1 e competitive ratio.