Sublinear Time Algorithm for Online Weighted Bipartite Matching

• URL: http://arxiv.org/abs/2208.03367v2
• Date: Mon, 12 Feb 2024 14:20:41 GMT
• Title: Sublinear Time Algorithm for Online Weighted Bipartite Matching
• Authors: Hang Hu, Zhao Song, Runzhou Tao, Zhaozhuo Xu, Junze Yin, Danyang Zhuo
• Abstract summary: Online bipartite matching is a fundamental problem in online algorithms. Weights are decided by the inner product between the deep representation of a user and the deep representation of an item. We show that, with our proposed randomized data structures, the weights can be computed in sublinear time while still preserving the competitive ratio of the matching algorithm.
• Score: 16.48305467237292
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Online bipartite matching is a fundamental problem in online algorithms. The goal is to match two sets of vertices to maximize the sum of the edge weights, where for one set of vertices, each vertex and its corresponding edge weights appear in a sequence. Currently, in the practical recommendation system or search engine, the weights are decided by the inner product between the deep representation of a user and the deep representation of an item. The standard online matching needs to pay $nd$ time to linear scan all the $n$ items, computing weight (assuming each representation vector has length $d$), and then deciding the matching based on the weights. However, in reality, the $n$ could be very large, e.g. in online e-commerce platforms. Thus, improving the time of computing weights is a problem of practical significance. In this work, we provide the theoretical foundation for computing the weights approximately. We show that, with our proposed randomized data structures, the weights can be computed in sublinear time while still preserving the competitive ratio of the matching algorithm.

Related papers

• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory. We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds. We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
  arXiv  Detail & Related papers  (2025-02-25T19:08:26Z)
• Scalable Private Partition Selection via Adaptive Weighting [66.09199304818928]
  In a private set union, users hold subsets of items from an unbounded universe. The goal is to output as many items as possible from the union of the users' sets while maintaining user-level differential privacy. We propose an algorithm for this problem, MaximumDegree (MAD), which adaptively reroutes weight from items with weight far above the threshold needed for privacy to items with smaller weight.
  arXiv  Detail & Related papers  (2025-02-13T01:27:11Z)
• Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
  We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium. We also give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium. Our algorithm for approximately optimal EFCE is, to our knowledge, the first that achieves 3 desiderata simultaneously.
  arXiv  Detail & Related papers  (2024-12-22T09:12:05Z)
• Pushing the Limits: Concurrency Detection in Acyclic Sound Free-Choice Workflow Nets in $O(P^2 + T^2)$ [0.8192907805418583]
  Knowing which places and transitions could be executed in parallel helps to understand computation nets. Kovalyov and Esparza have developed algorithms that compute all concurrent places in $Obig((P+T)TP2big)$ for live and bounded nets. This paper complements the palette of detection algorithms with the Concurrent Paths (CP) algorithm for sound free-choice workflow nets.
  arXiv  Detail & Related papers  (2024-01-29T12:11:34Z)
• Scalable network reconstruction in subquadratic time [0.0]
  We present a general algorithm applicable to a broad range of reconstruction problems that significantly outperforms this quadratic baseline. Our algorithm relies on a second neighbor search that produces the best edge candidates with high probability. We show that our algorithm achieves a performance that is many orders of magnitude faster than the quadratic baseline.
  arXiv  Detail & Related papers  (2024-01-02T19:00:13Z)
• Equivariant Deep Weight Space Alignment [54.65847470115314]
  We propose a novel framework aimed at learning to solve the weight alignment problem. We first prove that weight alignment adheres to two fundamental symmetries and then, propose a deep architecture that respects these symmetries.
  arXiv  Detail & Related papers  (2023-10-20T10:12:06Z)
• Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms [56.08144272945755]
  We compare 8 popular numerical black-box optimization algorithms on the $L_infty$ star discrepancy problem. We show that all used solvers perform very badly on a large majority of the instances. We suspect that state-of-the-art numerical black-box optimization techniques fail to capture the global structure of the problem.
  arXiv  Detail & Related papers  (2023-06-29T14:57:56Z)
• CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes [62.45415756883437]
  Jointly matching multiple, non-rigidly deformed 3D shapes is a challenging, $mathcalNP$-hard problem. Existing quantum shape-matching methods do not support multiple shapes and even less cycle consistency. This paper introduces the first quantum-hybrid approach for 3D shape multi-matching.
  arXiv  Detail & Related papers  (2023-03-28T17:59:55Z)
• An Improved Algorithm For Online Min-Sum Set Cover [0.45687771576879593]
  We study a model of online preference aggregation, where an algorithm maintains an ordered list of $n$ elements. We construct a computationally efficient randomized algorithm whose competitive ratio (ALG-to-OPT cost ratio) is $O(r2)$. This is the first algorithm whose ratio does not depend on $n$: the previously best algorithm for this problem was $O(r3/2 cdot sqrtn)$-competitive and $Omega(r)$ is a lower bound on the performance of any deterministic online algorithm.
  arXiv  Detail & Related papers  (2022-09-11T14:03:51Z)
• A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching [69.14632473279651]
  We present a scalable algorithm for globally optimizing over the space of geometrically consistent mappings between 3D shapes. We propose a novel primal coupled with a Lagrange dual problem that is several orders of magnitudes faster than previous solvers.
  arXiv  Detail & Related papers  (2022-04-27T09:47:47Z)
• Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach [5.683591363967851]
  We present an end-to-end Reinforcement Learning framework for deriving better matching policies based on trial-and-error on historical data. We show that most of the learning approaches perform significantly better than classical greedy algorithms on four synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-09-21T18:04:19Z)
• Metrical Task Systems with Online Machine Learned Advice [0.0]
  We show that augmenting online algorithms with a machine learned predictor can provably decrease the competitive ratio under as long as the predictor is suitably accurate. We focus on the specific class of uniform task systems on $n$ tasks, for which the best deterministic algorithm is $O(n)$ competitive and the best randomized algorithm is $O(log n)$ competitive.
  arXiv  Detail & Related papers  (2020-12-17T04:56:51Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.