>
you're reading...
Announcements

SACT Seminar: Revealing Optimal Thresholds for Generalized Secretary Problem Via Continuous LP

Time: 2:00pm Tuesday, 21st April.

Location: SIT 459

Speaker: Hubert Chan, The University of Hong Kong

Title: Revealing Optimal Thresholds for Generalized Secretary Problem
Via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random
Arrival Order

Abstract:

We consider the general (J, K)-secretary problem. An algorithm
observes the relative merits of arriving items and is allowed to make
J selections. The objective is to maximize the expected number of
items selected among the K best items. We give a construction
procedure for an optimal algorithm involving JK thresholds via a
continuous linear programming method. We further provide new results
on online K-item auction and bipartite K-matching with random arrival
order.

This is joint work with Fei Chen, Shaofeng H.-C. Jiang, and appears in
SODA 2015.

Advertisements

Discussion

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 64 other followers

%d bloggers like this: