7 papers · 1 filter
A 3.1462-Competitive Algorithm for Matroid Secretary
Hau Chan, Jianan Lin, Chenhao Wang
The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable deci…
Consistency-Robustness Tradeoffs for Strategyproof Scheduling with Predictions
Hau Chan, Jianan Lin, Chenhao Wang
We study strategyproof scheduling on \(n\) unrelated machines with predictions. Each machine is controlled by an agent with privately known processing times, while the mechanism re…
Sequential Phragmén Guarantees 2-Approximate Core Stability
Hau Chan, Jianan Lin, Chenhao Wang
In an approval-based committee election, a committee of size is selected from a set of candidates to represent voters of total weight , each of whom has positive weight and…
Randomized Strategyproof Facility Location: Two Facilities and Beyond
Hau Chan, Jianan Lin, Chenhao Wang
We design and analyze randomized strategyproof mechanisms for multi-facility location under the utilitarian social-cost objective, the sum of the agents' distances to their nearest…
Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules
Hau Chan, Jianan Lin, Chenhao Wang
In metric social choice, voters and candidates lie in a common but unknown metric space, voters rank candidates by distance, and a voting rule seeks to minimize total distance to t…
Strategyproof Mechanisms for Euclidean Facility Location Problems under -norm Social Cost
Hau Chan, Jianan Lin, Chenhao Wang
We study strategyproof mechanisms for eliciting agents' location preferences truthfully in the Euclidean plane and locating a facility so as to minimize the -nor…
Mechanism Design for Connecting Regions Under Disruptions
Hau Chan, Jianan Lin, Zining Qin +1
Man-made and natural disruptions such as planned constructions on roads, suspensions of bridges, and blocked roads by trees/mudslides/floods can often create obstacles that separat…