Search

We consider the unweighted bipartite maximum matching problem in the one-pass turnstile streaming model where the input stream consists of edge insertions and deletions. In the insertion-only model, a one-pass 2-approximation streaming algorithm can be easily obtained with space O(n logn), where n denotes the number of vertices of the input graph. We show that no such result is possible if edge deletions are allowed, even if space O(n3/2 − δ) is granted, for every δ > 0. Specifically, for every 0 ≤ e ≤ 1, we show that in the one-pass turnstile streaming model, in order to compute a O(n e )-approximation, space Ω(n3/2 − 4e) is required for constant error randomized algorithms, and, up to logarithmic factors, space \(\tilde{\mathrm{O}}( n^{2-2\epsilon} )\) is sufficient.

While the previous chapter gave you several algorithms for a single problem, this chapter describes a single algorithm with many variations and applications. The core problem is that of finding maximum flow in a network, and the main solution strategy I’ll be using is the augmenting path method of Ford and Fulkerson. Before tackling the full problem, I’ll guide you through two simpler problems, which are basically special cases (they’re easily reduced to maximum flow). These problems, bipartite matching and disjoint paths, have many applications themselves and can be solved by more specialized algorithms. You’ll also see that the max-flow problem has a dual, the min-cut problem, which means that you’ll automatically solve both problems at the same time. The min-cut problem has several interesting applications that seem very different from those of max-flow, even if they are really closely related. Finally, I’ll give you some pointers on one way of extending the max-flow problem, by adding costs, and looking for the cheapest of the maximum flows, paving the way for applications such as mincost bipartite matching.

Faced with the imminent retirement of two senior employees who used to make decisions on bus allocations to customers manually, a bus rental company in Seoul, South Korea, asked us to develop a DMSS (decision-making support system) to help the young fresh graduate employee who will be taking over this job from them. Practice has shown that allocation and routing decisions made manually by human operators with long experience are usually nearly optimal, and it is very hard to beat those decisions using a computerized DMSS. Therefore the company asked us to design an i-DMSS (intelligent DMSS) that can help the new decision maker to reach decisions comparable in quality to those made by the retiring pair of senior decision makers. In this paper we discuss this decision problem, its context, the models we used to solve it, the algorithms we used in the i-DMSS to solve these models, and how this i-DMSS is used to make the decisions daily. The i-DMSS is based on bipartite matching and transportation algorithms and heuristics, and produces solutions 10–20% more economical than the manual decisions.

We consider the problem of finding a popular matching in the Capacitated House Allocation problem (CHA). An instance of CHA involves a set of agents and a set of houses. Each agent has a preference list in which a subset of houses are ranked in strict order, and each house may be matched to a number of agents that must not exceed its capacity. A matching M is popular if there is no other matching M' such that the number of agents who prefer their allocation in M' to that in M exceeds the number of agents who prefer their allocation in M to that in M'. Here, we give an O(√Cn1+m)algorithm to determine if an instance of CHA admits a popular matching, and if so, to find a largest such matching, where C is the total capacity of the houses, n1 is the number of agents and m is the total length of the agents' preference lists. For the case where preference lists may contain ties, we give an O(√Cn1)+m) algorithm for the analogous problem.