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/

Global: Zendy Tools annual

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

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The classical Prophet Inequality arises from a fundamental problem inoptimal-stopping theory. In this problem, a gambler sees a finite sequence ofindependent, non-negative random variables. If he stops the sequence at anytime, he collects a reward equal to the most recent observation. The ProphetInequality states that, knowing the distribution of each random variable, thegambler can achieve at least half as much reward in expectation, as a prophetwho knows the entire sample path of random variables (Krengel and Sucheston1978). In this paper, we prove a corresponding bound for correlatednon-negative random variables. We analyze two methods for proving the bound, aconstructive approach, which produces a worst-case instance, and a reductiveapproach, which characterizes a certain submartingale arising from the rewardprocess of our online algorithm. We apply this new prophet inequality to thedesign of algorithms for a class of two-sided bipartite matching problems thatunderlie online task assignment problems. In these problems, demand units ofvarious types arrive randomly and sequentially over time according to somestochastic process. Tasks, or supply units, arrive according to anotherstochastic process. Each demand unit must be irrevocably matched to a supplyunit or rejected. The match earns a reward that depends on the pair. Theobjective is to maximize the total expected reward over the planning horizon.The problem arises in mobile crowd-sensing and crowd sourcing contexts, whereworkers and tasks must be matched by a platform according to various criteria.We derive the first online algorithms with worst-case performance guaranteesfor our class of two-sided bipartite matching problems.

Prophet Inequality with Correlated Arrival Probabilities, with Application to Two Sided Matchings