Optimization and Search Problems
351 papers on this topic
Online Fair Division for Personalized $2$-Value Instances
We study an online fair division setting, where goods arrive one at a time and there is a fixed set of $n$ agents, each of whom has an additive valuation function over the goods. Once a good...
Understanding EFX Allocations: Counting and Variants
Envy-freeness up to any good (EFX) is a popular and important fairness property in the fair allocation of indivisible goods, of which its existence in general is still an open question. In this...
Automating Food Drop: The Power of Two Choices for Dynamic and Fair Food Allocation
Food waste and food insecurity are two closely related pressing global issues. Food rescue organizations worldwide run programs aimed at addressing the two problems. In this paper, we partner with...
Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
One-max search is a classic problem in online decision-making, in which a trader acts on a sequence of revealed prices and accepts one of them irrevocably to maximise its profit. The problem has...
Best-Arm Identification in Unimodal Bandits
We study the fixed-confidence best-arm identification problem in unimodal bandits, in which the means of the arms increase with the index of the arm up to their maximum, then decrease. We derive...
Detection Augmented Bandit Procedures for Piecewise Stationary MABs: A Modular Approach
Conventional Multi-Armed Bandit (MAB) algorithms are designed for stationary environments, where the reward distributions associated with the arms do not change with time. In many applications,...
Run for Cover: Dominating Set via Mobile Agents
Research involving computing with mobile agents is a fast-growing field, given the advancement of technology in automated systems, e.g., robots, drones, self-driving cars, etc. Therefore, it is...
Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback
We investigate the problem of unconstrained combinatorial multi-armed bandits with full-bandit feedback and stochastic rewards for submodular maximization. Previous works investigate the same...
Time Optimal Ergodic Search
Robots with the ability to balance time against the thoroughness of search have the potential to provide time-critical assistance in applications such as search and rescue. Current advances in...
Resource Allocation under the Latin Square Constraint
A Latin square is an $n \times n$ matrix filled with $n$ distinct symbols, each of which appears exactly once in each row and exactly once in each column. We introduce a problem of allocating $n$...
Prophet Inequalities Require Only a Constant Number of Samples
In a prophet inequality problem, $n$ independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent value as reward....
Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations
We study fair allocation of indivisible goods when agents have matroid rank valuations. Our main contribution is a simple algorithm based on the colloquial Yankee Swap procedure that computes...
The Bakers and Millers Game with Restricted Locations
We study strategic location choice by customers and sellers, termed the Bakers and Millers Game in the literature. In our generalized setting, each miller can freely choose any location for...
Incentivized Exploration of Non-Stationary Stochastic Bandits
We study incentivized exploration for the multi-armed bandit (MAB) problem with non-stationary reward distributions, where players receive compensation for exploring arms other than the greedy...
Distributed MIS with Low Energy and Time Complexities
We present randomized distributed algorithms for the maximal independent set problem (MIS) that, while keeping the time complexity nearly matching the best known, reduce the energy complexity...
Optimal foraging strategies can be learned
The foraging behavior of animals is a paradigm of target search in nature. Understanding which foraging strategies are optimal and how animals learn them are central challenges in modeling animal...
Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare
In many public health settings, it is important for patients to adhere to health programs, such as taking medications and periodic health checks. Unfortunately, beneficiaries may gradually...
Prophet Secretary Against the Online Optimal
We study the prophet secretary problem, a well-studied variant of the classic prophet inequality, where values are drawn from independent known distributions but arrive in uniformly random order....