English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The Bayesian online selection problem aims to design a pricing scheme for asequence of arriving buyers that maximizes the expected social welfare (orrevenue) subject to different structural constraints. Inspired by applicationswith a hierarchy of service, this paper focuses on the cases where a laminarmatroid characterizes the set of served buyers. We give the firstPolynomial-Time Approximation Scheme (PTAS) for the problem when the laminarmatroid has constant depth. Our approach is based on rounding the solution of ahierarchy of linear programming relaxations that approximate the optimum onlinesolution with any degree of accuracy, plus a concentration argument showingthat rounding incurs a small loss. We also study another variation, which wecall the production-constrained problem. The allowable set of served buyers ischaracterized by a collection of production and shipping constraints that forma particular example of a laminar matroid. Using a similar LP-based approach,we design a PTAS for this problem, although in this special case the depth ofthe underlying laminar matroid is not necessarily a constant. The analysisexploits the negative dependency of the optimum selection rule in the lowerlevels of the laminar family. Finally, to demonstrate the generality of ourtechnique, we employ the linear programming-based approach employed in thepaper to re-derive some of the classic prophet inequalities known in theliterature -- as a side result.

Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection