research
∙
09/09/2023
Two-State Spin Systems with Negative Interactions
We study the approximability of computing the partition functions of two...
share
research
∙
08/09/2023
A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problem
For prohibitively large-scale Travelling Salesman Problems (TSPs), exist...
research
∙
07/10/2023
Auction Design for Value Maximizers with Budget and Return-on-spend Constraints
The paper designs revenue-maximizing auction mechanisms for agents who a...
research
∙
02/22/2023
Improved Coresets for Clustering with Capacity and Fairness Constraints
We study coresets for clustering with capacity and fairness constraints....
research
∙
01/20/2023
Coresets for Clustering with General Assignment Constraints
Designing small-sized coresets, which approximately preserve the costs o...
research
∙
11/20/2022
Bidder Subset Selection Problem in Auction Design
Motivated by practical concerns in the online advertising industry, we s...
research
∙
10/12/2022
Better Approximation for Interdependent SOS Valuations
Submodular over signal (SOS) defines a family of interesting functions f...
research
∙
07/10/2022
The Price of Stability for First Price Auction
This paper establishes the Price of Stability (PoS) for First Price Auct...
research
∙
07/05/2022
First Price Auction is 1 - 1/e^2 Efficient
We prove that the PoA of First Price Auctions is 1 - 1/e^2 ≈ 0.8647, clo...
research
∙
05/23/2022
Mechanism Design with Predictions
Improving algorithms via predictions is a very active research topic in ...
research
∙
11/20/2021
Oblivious Online Contention Resolution Schemes
Contention resolution schemes (CRSs) are powerful tools for obtaining "e...
research
∙
06/19/2021
Variance-Dependent Best Arm Identification
We study the problem of identifying the best arm in a stochastic multi-a...
research
∙
02/15/2021
Tight Revenue Gaps among Multi-Unit Mechanisms
This paper considers Bayesian revenue maximization in the k-unit setting...
research
∙
10/31/2020
Generalized Sorting with Predictions
Generalized sorting problem, also known as sorting with forbidden compar...
research
∙
12/20/2019
Learning Reserve Prices in Second-Price Auctions
This paper proves the tight sample complexity of Second-Price Auction w...
research
∙
11/27/2019
Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler
The algorithm and complexity of approximating the permanent of a matrix ...
research
∙
07/21/2019
Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio
In this paper, we study the two-facility location game on a line with op...
research
∙
07/14/2019
Zeros of ferromagnetic 2-spin systems
We study zeros of the partition functions of ferromagnetic 2-state spin ...
research
∙
07/10/2019
An algorithmic framework for approximating maximin share allocation of chores
In this paper, we consider the problem of how to fairly dividing m indiv...
research
∙
03/18/2019
Counting independent sets and colorings on random regular bipartite graphs
We give a fully polynomial-time approximation scheme (FPTAS) to count th...
research
∙
03/03/2019
Revenue Maximization with Imprecise Distribution
We study the revenue maximization problem with an imprecisely estimated ...
research
∙
02/12/2019
Optimal Budget-Feasible Mechanisms for Additive Valuations
In this paper, we obtain tight approximation guarantee for budget-feasib...
research
∙
11/07/2018
Approximability of the Eight-vertex Model
We initiate a study of the classification of approximation complexity of...
research
∙
11/02/2018
Tight Approximation Ratio of Anonymous Pricing
We consider two canonical Bayesian mechanism design settings. In the sin...
research
∙
07/24/2018
Zeros of Holant problems: locations and algorithms
We present fully polynomial-time (deterministic or randomised) approxima...
research
∙
04/20/2018
Bayesian Auctions with Efficient Queries
Generating good revenue is one of the most important problems in Bayesia...
research
∙
04/02/2018
Tight Revenue Gaps among Simple Mechanisms
We consider the simplest and most fundamental problem of selling a singl...
research
∙
12/16/2017
Approximability of the Six-vertex Model
In this paper we take the first step toward a classification of the appr...
research
∙
11/09/2017
Counting hypergraph colorings in the local lemma regime
We give a fully polynomial-time approximation scheme (FPTAS) to count th...
research
∙
10/20/2016