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

推荐订阅源

大猫的无限游戏
大猫的无限游戏
D
DataBreaches.Net
M
MIT News - Artificial intelligence
量子位
N
Netflix TechBlog - Medium
The Cloudflare Blog
The GitHub Blog
The GitHub Blog
P
Proofpoint News Feed
人人都是产品经理
人人都是产品经理
B
Blog RSS Feed
B
Blog
博客园_首页
博客园 - Franky
MyScale Blog
MyScale Blog
有赞技术团队
有赞技术团队
Apple Machine Learning Research
Apple Machine Learning Research
MongoDB | Blog
MongoDB | Blog
云风的 BLOG
云风的 BLOG
爱范儿
爱范儿
H
Help Net Security
Y
Y Combinator Blog
Stack Overflow Blog
Stack Overflow 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
Optimal Groupon Allocations
Weihao Kong, Jian Li, Tao Qin, Tie-Yan Liu · 2013-05-26 · via cs.DS updates on arXiv.org

Group-buying websites represented by Groupon.com are very popular in electronic commerce and online shopping nowadays. They have multiple slots to provide deals with significant discounts to their visitors every day. The current user traffic allocation mostly relies on human decisions. We study the problem of automatically allocating the user traffic of a group-buying website to different deals to maximize the total revenue and refer to it as the Group-buying Allocation Problem (\GAP). The key challenge of \GAP\ is how to handle the tipping point (lower bound) and the purchase limit (upper bound) of each deal. We formulate \GAP\ as a knapsack-like problem with variable-sized items and majorization constraints. Our main results for \GAP\ can be summarized as follows. (1) We first show that for a special case of \GAP, in which the lower bound equals the upper bound for each deal, there is a simple dynamic programming-based algorithm that can find an optimal allocation in pseudo-polynomial time. (2) The general case of \GAP\ is much more difficult than the special case. To solve the problem, we first discover several structural properties of the optimal allocation, and then design a two-layer dynamic programming-based algorithm leveraging those properties. This algorithm can find an optimal allocation in pseudo-polynomial time. (3) We convert the two-layer dynamic programming based algorithm to a fully polynomial time approximation scheme (FPTAS), using the technique developed in \cite{ibarra1975fast}, combined with some careful modifications of the dynamic programs. Besides these results, we further investigate some natural generalizations of \GAP, and propose effective algorithms.