Matching markets with historical data are abundant in many applications, e.g., matching candidates to jobs in hiring, workers to tasks in crowdsourcing markets, and jobs to servers in cloud services. In all these applications, a match consumes one or more shared and limited resources and the goal is to best utilize these to maximize a global objective. Additionally, one often has historical data and hence some statistics (usually firstorder moments) of the arriving agents (e.g., candidates, workers, and jobs) can be learnt. To model these scenarios, we propose a unifying framework, called Multi Budgeted Online Assignment with Known Adversarial Distributions. In this model,we have a set of offline servers with different deadlines and a set of online job types. At each time, a job of type j arrives. Assigning this job to a server i yields a profit w(i, j) while consuming a(i,j)  a vector lying in [0, 1]^K  quantities of distinct resources. The goal is to design an (online) assignment policy that maximizes the total expected profit without violating the (hard) budget constraint. We propose and theoretically analyze two linear programming (LP) based algorithms which are almost optimal among all LPbased approaches. We also propose several heuristicsmore »
Online and Offline Algorithms for Circuit Switch Scheduling
Motivated by the use of high speed circuit switches in large scale data centers, we consider the problem of circuit switch scheduling. In this problem we are given demands between pairs of servers and the goal is to schedule at every time step a matching between the servers while maximizing the total satisfied demand over time. The crux of this scheduling problem is that once one shifts from one matching to a different one a fixed delay delta is incurred during which no data can be transmitted. For the offline version of the problem we present a (1(1/e)epsilon) approximation ratio (for any constant epsilon >0). Since the natural linear programming relaxation for the problem has an unbounded integrality gap, we adopt a hybrid approach that combines the combinatorial greedy with randomized rounding of a different suitable linear program. For the online version of the problem we present a (bicriteria) ((e1)/(2e1)epsilon)competitive ratio (for any constant epsilon >0 ) that exceeds time by an additive factor of O(delta/epsilon). We note that no unicriteria online algorithm is possible. Surprisingly, we obtain the result by reducing the online version to the offline one.
 Award ID(s):
 1717947
 Publication Date:
 NSFPAR ID:
 10178887
 Journal Name:
 Leibniz international proceedings in informatics
 Volume:
 150
 Page Range or eLocationID:
 27:127:14
 ISSN:
 18688969
 Sponsoring Org:
 National Science Foundation
More Like this


Bipartite matching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartite matching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this paper, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions (OMRRKAD), in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LPbased adaptive algorithm that achieves an online competitive ratio of 1/2  epsilon for any given epsilon > 0. We also show that no nonadaptive algorithm can achieve a ratio of 1/2 + o(1) based on the same benchmark LP. Through a datadriven analysis on a massive openlyavailable dataset, we show our model is robust enough to capture the application of taxi dispatching services and ridesharing systems. We also present heuristics that perform well in practice.

We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartite graph G(A cup B,E) with edge weights of 0 or 1. Let w <= n be an upper bound on the weight of any matching in G. Consider the subgraph induced by all the edges of G with a weight 0. Suppose every connected component in this subgraph has O(r) vertices and O(mr/n) edges. We present an algorithm to compute a maximum cardinality matching in G in O~(m(sqrt{w} + sqrt{r} + wr/n)) time. When all the edge weights are 1 (symmetrically when all weights are 0), our algorithm will be identical to the wellknown HopcroftKarp (HK) algorithm, which runs in O(m sqrt{n}) time. However, if we can carefully assign weights of 0 and 1 on its edges such that both w and r are sublinear in n and wr=O(n^{gamma}) for gamma < 3/2, then we can compute maximum cardinality matching in G in o(m sqrt{n}) time. Using our algorithm, we obtain a new O~(n^{4/3}/epsilon^4) time algorithm to compute an epsilonapproximate bottleneck matching of A,B subsetR^2 and an 1/(epsilon^{O(d)}}n^{1+(d1)/(2d1)}) poly logmore »

Bipartitematching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartitematching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this article, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions ( OMRRKAD ) , in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LPbased nonadaptive algorithm that achieves an online competitive ratio of ½ϵ for any given constant ϵ > 0. We also show that no adaptive algorithm can achieve a ratio of ½ + o (1) based on the same benchmark LP. Through a datadriven analysis on a massive openly available dataset, we show our model is robust enough to capture the application of taxi dispatching services and ridesharing systems. We also present heuristics that perform well in practice.

Abstract We consider the problem of computing the partition function $\sum _x e^{f(x)}$ , where $f: \{1, 1\}^n \longrightarrow {\mathbb R}$ is a quadratic or cubic polynomial on the Boolean cube $\{1, 1\}^n$ . In the case of a quadratic polynomial f , we show that the partition function can be approximated within relative error $0 < \epsilon < 1$ in quasipolynomial $n^{O(\ln n  \ln \epsilon )}$ time if the Lipschitz constant of the nonlinear part of f with respect to the $\ell ^1$ metric on the Boolean cube does not exceed $1\delta $ , for any $\delta>0$ , fixed in advance. For a cubic polynomial f , we get the same result under a somewhat stronger condition. We apply the method of polynomial interpolation, for which we prove that $\sum _x e^{\tilde {f}(x)} \ne 0$ for complexvalued polynomials $\tilde {f}$ in a neighborhood of a realvalued f satisfying the above mentioned conditions. The bounds are asymptotically optimal. Results on the zerofree region are interpreted as the absence of a phase transition in the Lee–Yang sense in the corresponding Ising model. The novel feature of the bounds is that they control the total interaction of each vertex but notmore »