# Greedy Algorithm for Multiway Matching with Bounded Regret

arXiv: https://arxiv.org/abs/2112.04622 · HTML: https://mlsanity.com/paper/2112.04622/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Dec 2021.

## Built on by (most cited first, 7 of 7)

- [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [L0-Regularized Quadratic Surface Support Vector Machines](https://mlsanity.com/paper/2501.11268/) (2025)
- [A Learning-Based Hybrid Decision Framework for Matching Systems with User Departure Detection](https://mlsanity.com/paper/2602.22412/) (2026)
- [BESplit: Bias-Compensated Split Federated Learning with Evidential Aggregation](https://mlsanity.com/paper/2605.17508/) (2026)
- [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (2026)
- [A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret](https://mlsanity.com/paper/2609.05895/) (2026)

## Abstract (arXiv)

In this paper we prove the efficacy of a simple greedy algorithm for a finite horizon online resource allocation/matching problem, when the corresponding static planning linear program (SPP) exhibits a non-degeneracy condition called the general position gap (GPG). The key intuition that we formalize is that the solution of the reward maximizing SPP is the same as a feasibility Linear Program restricted to the optimal basic activities, and under GPG this solution can be tracked with bounded regret by a greedy algorithm, i.e., without the commonly used technique of periodically resolving the SPP. The goal of the decision maker is to combine resources (from a finite set of resource types) into configurations (from a finite set of feasible configurations) where each configuration is specified by the number of resources consumed of each type and a reward. The resources are further subdivided into three types - offline (whose quantity is known and available at time 0), online-queueable (which arrive online and can be stored in a buffer), and online-nonqueueable (which arrive online and must be matched on arrival or lost). Under GRG we prove that, (i) our greedy algorithm gets bounded any-time regret of O(1/ε0) for matching reward (ε0 is a measure of the GPG) when no configuration contains both an online-queueable and an online-nonqueueable resource, and (ii) O(log t) expected any-time regret otherwise (we also prove a matching lower bound). By considering the three types of resources, our matching framework encompasses several well-studied problems such as dynamic multi-sided matching, network revenue management, online stochastic packing, and multiclass queueing systems.