research
∙
08/23/2023
On the Existence of EFX (and Pareto-Optimal) Allocations for Binary Chores
We study the problem of allocating a group of indivisible chores among a...
share
research
∙
07/10/2023
One Quarter Each (on Average) Ensures Proportionality
We consider the problem of fair allocation of m indivisible items to a g...
research
∙
06/23/2023
Improved Competitive Ratios for Online Bipartite Matching on Degree Bounded Graphs
We consider the online bipartite matching problem on (k,d)-bounded graph...
research
∙
04/26/2023
Multi-agent Online Scheduling: MMS Allocations for Indivisible Items
We consider the problem of fairly allocating a sequence of indivisible i...
research
∙
02/11/2023
Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching
We consider the edge-weighted online stochastic matching problem, in whi...
research
∙
01/19/2023
Weighted EF1 Allocations for Indivisible Chores
We study how to fairly allocate a set of indivisible chores to a group o...
research
∙
11/24/2022
Multiagent MST Cover: Pleasing All Optimally via A Simple Voting Rule
Given a connected graph on whose edges we can build roads to connect the...
research
∙
05/11/2022
Query Efficient Prophet Inequality with Unknown I.I.D. Distributions
We study the single-choice prophet inequality problem, where a gambler f...
research
∙
04/26/2022
Mixed Strategies for Security Games with General Defending Requirements
The Stackelberg security game is played between a defender and an attack...
research
∙
02/17/2022
Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions
The theory of algorithmic fair allocation is within the center of multi-...
research
∙
01/24/2022
Generalized Spatially-Coupled Parallel Concatenated Codes With Partial Repetition
A new class of spatially-coupled turbo-like codes (SC-TCs), dubbed gener...
research
∙
09/15/2021
Approximately EFX Allocations for Indivisible Chores
In this paper we study how to fairly allocate a set of m indivisible cho...
research
∙
06/28/2021
Approximately Envy-Free Budget-Feasible Allocation
In the budget-feasible allocation problem, a set of items with varied si...
research
∙
05/03/2021
Generalized Spatially Coupled Parallel Concatenated Convolutional Codes With Partial Repetition
We introduce generalized spatially coupled parallel concatenated codes (...
research
∙
03/22/2021
Almost Proportional Allocations for Indivisible Chores
In this paper, we consider how to fairly allocate m indivisible chores t...
research
∙
12/27/2020
Approximate and Strategyproof Maximin Share Allocation of Chores with Ordinal Preferences
We initiate the work on maximin share (MMS) fair allocation of m indivis...
research
∙
12/24/2020
Analysis and Design of Partially Information- and Partially Parity-Coupled Turbo Codes
In this paper, we study a class of spatially coupled turbo codes, namely...
research
∙
12/07/2020
Budget-feasible Maximum Nash Social Welfare Allocation is Almost Envy-free
The Nash social welfare (NSW) is a well-known social welfare measurement...
research
∙
12/02/2020
Defending against Contagious Attacks on a Network with Resource Reallocation
In classic network security games, the defender distributes defending re...
research
∙
06/22/2020
Partially Information Coupled Duo-Binary Turbo Codes
Partially information coupled turbo codes (PIC-TCs) is a class of spatia...
research
∙
05/13/2020
Fully Online Matching II: Beating Ranking and Water-filling
Karp, Vazirani, and Vazirani (STOC 1990) initiated the study of online b...
research
∙
02/25/2020
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
In the dynamic minimum set cover problem, a challenge is to minimize the...
research
∙
02/25/2020
An Improved Algorithm for Dynamic Set Cover
We consider the minimum set cover problem in a dynamic setting. Here, we...
research
∙
02/14/2020
A Simple 1-1/e Approximation for Oblivious Bipartite Matching
We study the oblivious matching problem, which aims at finding a maximum...
research
∙
02/12/2020
Recreating Bat Behavior on Quad-rotor UAVs-A Simulation Approach
We develop an effective computer model to simulate sensing environments ...
research
∙
01/13/2020
Simulate forest trees by integrating L-system and 3D CAD files
In this article, we propose a new approach for simulating trees, includi...
research
∙
11/19/2019
Defending with Shared Resources on a Network
In this paper we consider a defending problem on a network. In the model...
research
∙
10/08/2019
Upper and Lower Bounds for Fully Retroactive Graph Problems
Classic dynamic data structure problems maintain a data structure subjec...
research
∙
09/10/2019
Well-behaved Online Load Balancing Against Strategic Jobs
In the online load balancing problem on related machines, we have a set ...
research
∙
07/11/2019
Perturbed Greedy on Oblivious Matching Problems
We study the maximum matching problem in the oblivious setting, i.e. the...
research
∙
06/16/2019
Density Evolution Analysis of Partially Information Coupled Turbo Codes on the Erasure Channel
In this paper, we investigate the performance of a class of spatially co...
research
∙
05/23/2019
Maximin-Aware Allocations of Indivisible Goods
We study envy-free allocations of indivisible goods to agents in setting...
research
∙
05/22/2019
Strategyproof and Approximately Maxmin Fair Share Allocation of Chores
We initiate the work on fair and strategyproof allocation of indivisible...
research
∙
10/18/2018
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Huang et al. (STOC 2018) introduced the fully online matching problem, a...
research
∙
06/06/2018
Online Makespan Minimization: The Power of Restart
We consider the online makespan minimization problem on identical machin...
research
∙
04/20/2018
Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals
We introduce a weighted version of the ranking algorithm by Karp et al. ...
research
∙
02/12/2018
How to Match when All Vertices Arrive Online
We introduce a fully online model of maximum cardinality matching in whi...
research
∙
11/05/2017