research
∙
09/19/2023
Online Matching with Stochastic Rewards: Advanced Analyses Using Configuration Linear Programs
Mehta and Panigrahi (2012) proposed Online Matching with Stochastic Rewa...
share
research
∙
08/19/2023
Laminar Matroid Secretary: Greedy Strikes Back
We show that a simple greedy algorithm is 4.75 probability-competitive f...
research
∙
08/17/2023
Simpler Analyses of Union-Find
We analyze union-find using potential functions motivated by continuous ...
research
∙
03/11/2023
E2CoPre: Energy Efficient and Cooperative Collision Avoidance for UAV Swarms with Trajectory Prediction
This paper addresses the collision avoidance problem of UAV swarms in th...
research
∙
12/01/2022
Tight Conditional Lower Bounds for Vertex Connectivity Problems
We study the fine-grained complexity of graph connectivity problems in u...
research
∙
11/28/2022
OpTree: An Efficient Algorithm for All-gather Operation in Optical Interconnect Systems
All-gather collective communication is one of the most important communi...
research
∙
11/06/2022
Online Nash Welfare Maximization Without Predictions
Nash welfare maximization is widely studied because it balances efficien...
research
∙
07/22/2022
WRHT: Efficient All-reduce for Distributed DNN Training in Optical Interconnect System
Communication efficiency plays an important role in accelerating the dis...
research
∙
05/17/2022
Deterministic 3-Server on a Circle and the Limitation of Canonical Potentials
The deterministic k-server conjecture states that there is a k-competiti...
research
∙
05/17/2022
Strong Revenue (Non-)Monotonicity of Single-parameter Auctions
Consider Myerson's optimal auction with respect to an inaccurate prior, ...
research
∙
04/19/2022
Multi-UAV Collision Avoidance using Multi-Agent Reinforcement Learning with Counterfactual Credit Assignment
Multi-UAV collision avoidance is a challenging task for UAV swarm applic...
research
∙
03/07/2022
Class Fairness in Online Matching
In the classical version of online bipartite matching, there is a given ...
research
∙
03/06/2022
The Power of Multiple Choices in Online Stochastic Matching
We study the power of multiple choices in online stochastic matching. De...
research
∙
11/19/2021
Adversarial Deep Learning for Online Resource Allocation
Online algorithm is an important branch in algorithm design. Designing o...
research
∙
09/30/2021
Accelerating Fully Connected Neural Network on Optical Network-on-Chip (ONoC)
Fully Connected Neural Network (FCNN) is a class of Artificial Neural Ne...
research
∙
06/08/2021
Improved Online Correlated Selection
This paper studies the online correlated selection (OCS) problem introdu...
research
∙
05/11/2021
Targeting Makes Sample Efficiency in Auction Design
This paper introduces the targeted sampling model in optimal auction des...
research
∙
05/08/2021
E^2Coop: Energy Efficient and Cooperative Obstacle Detection and Avoidance for UAV Swarms
Energy efficiency is of critical importance to trajectory planning for U...
research
∙
03/24/2021
Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program
We study the online stochastic matching problem. Consider a bipartite gr...
research
∙
09/09/2020
Adwords in a Panorama
Three decades ago, Karp, Vazirani, and Vazirani (STOC 1990) defined the ...
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
∙
05/05/2020
Towards QoS-Aware and Resource-Efficient GPU Microservices Based on Spatial Multitasking GPUs In Datacenters
While prior researches focus on CPU-based microservices, they are not ap...
research
∙
05/05/2020
Edge-Weighted Online Bipartite Matching
Online bipartite matching and its variants are among the most fundamenta...
research
∙
02/05/2020
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue
Mehta and Panigrahi (FOCS 2012) introduce the problem of online matching...
research
∙
12/12/2019
Algorithmic Price Discrimination
We consider a generalization of the third degree price discrimination pr...
research
∙
11/27/2019
Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem
This paper explores a theory of generalization for learning problems on ...
research
∙
10/08/2019
Understanding Zadimoghaddam's Edge-weighted Online Matching Algorithm: Weighted Case
This article presents a simplification of Zadimoghaddam's algorithm for ...
research
∙
10/07/2019
Understanding Zadimoghaddam's Edge-weighted Online Matching Algorithm: Unweighted Case
This article identifies a key algorithmic ingredient in the edge-weighte...
research
∙
07/17/2019
In-Depth Benchmarking of Graph Database Systems with the Linked Data Benchmark Council (LDBC) Social Network Benchmark (SNB)
In this study, we present the first results of a complete implementation...
research
∙
05/02/2019
Near Optimal Jointly Private Packing Algorithms via Dual Multiplicative Weight Update
We present an improved (ϵ, δ)-jointly differentially private algorithm f...
research
∙
05/02/2019
Scalable and Jointly Differentially Private Packing
We introduce an (ϵ, δ)-jointly differentially private algorithm for pack...
research
∙
04/10/2019
Settling the Sample Complexity of Single-parameter Revenue Maximization
This paper settles the sample complexity of single-parameter revenue max...
research
∙
12/31/2018
Vehicles to Pedestrians Signal Transmissions Based on Cloud Computing
Collisions between vehicles and pedestrians usually result in the fatali...
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/30/2018
Learning Optimal Reserve Price against Non-myopic Bidders
We consider the problem of learning optimal reserve price in repeated au...
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
∙
12/14/2017
Linear time Minimum Area All-flush Triangles Circumscribing a Convex Polygon
We study the problem of computing the minimum area triangle that circums...
research
∙
12/14/2017
Minimum Area All-flush Triangles Circumscribing a Convex Polygon
In this paper, we consider the problem of computing the minimum area tri...
research
∙
05/26/2017
Online Auctions and Multi-scale Online Learning
We consider revenue maximization in online auctions and pricing. A selle...
research
∙
10/07/2015