惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

D
Docker
博客园 - 【当耐特】
S
SegmentFault 最新的问题
阮一峰的网络日志
阮一峰的网络日志
大猫的无限游戏
大猫的无限游戏
WordPress大学
WordPress大学
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
The Cloudflare Blog
Apple Machine Learning Research
Apple Machine Learning Research
小众软件
小众软件
博客园 - 三生石上(FineUI控件)
Martin Fowler
Martin Fowler
云风的 BLOG
云风的 BLOG
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
F
Fortinet All Blogs
Y
Y Combinator Blog
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
J
Java Code Geeks
Engineering at Meta
Engineering at Meta
MyScale Blog
MyScale Blog
B
Blog
酷 壳 – CoolShell
酷 壳 – CoolShell
人人都是产品经理
人人都是产品经理

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
On price-induced minmax matchings
Christoph Dürr, Mathieu Mari, Ulrike Schmidt-Kraepelin · 2023-02-23 · via cs.DS updates on arXiv.org

We study a natural combinatorial pricing problem for sequentially arriving buyers with equal budgets. Each buyer is interested in exactly one pair of items and purchases this pair if and only if, upon arrival, both items are still available and the sum of the item prices does not exceed the budget. The goal of the seller is to set prices to the items such that the number of transactions is maximized when buyers arrive in adversarial order. Formally, we are given an undirected graph where vertices represent items and edges represent buyers. Once prices are set to the vertices, edges with a total price exceeding the buyers' budgets are evicted. Any arrival order of the buyers leads to a set of transactions that forms a maximal matching in this subgraph, and an adversarial arrival order results in a minimum maximal matching. In order to measure the performance of a pricing strategy, we compare the size of such a matching to the size of a maximum matching in the original graph. It was shown by Correa et al. [IPCO 2022] that the best ratio any pricing strategy can guarantee lies within $[1/2, 2/3]$. Our contribution to the problem is two-fold: First, we provide several characterizations of subgraphs that may result from pricing schemes. Second, building upon these, we show an improved upper bound of $3/5$ and a lower bound of $1/2 + 2/n$, where $n$ is the number of items.