research
∙
09/20/2023
Testing frequency distributions in a stream
We study how to verify specific frequency distributions when we observe ...
share
research
∙
10/07/2022
An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees
In the Distance-constrained Vehicle Routing Problem (DVRP), we are given...
research
∙
09/12/2022
Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm
In the unsplittable capacitated vehicle routing problem, we are given a ...
research
∙
02/11/2022
A Tight (3/2+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees
We give a polynomial time (3/2+ϵ)-approximation algorithm for the unspli...
research
∙
12/08/2021
A Simple Algorithm for Graph Reconstruction
How efficiently can we find an unknown graph using distance queries betw...
research
∙
11/05/2021
A PTAS for Capacitated Vehicle Routing on Trees
We give a polynomial time approximation scheme (PTAS) for the unit deman...
research
∙
09/19/2021
Constrained School Choice with Incomplete Information
School choice is the two-sided matching market where students (on one si...
research
∙
09/14/2021
Probabilistic Analysis of Euclidean Capacitated Vehicle Routing
We give a probabilistic analysis of the unit-demand Euclidean capacitate...
research
∙
08/09/2021
Apportionment with Parity Constraints
In the classic apportionment problem the goal is to decide how many seat...
research
∙
11/05/2020
Competitive Data-Structure Dynamization
Data-structure dynamization is a general approach for making static data...
research
∙
10/15/2020
Large Very Dense Subgraphs in a Stream of Edges
We study the detection and the reconstruction of a large very dense subg...
research
∙
05/01/2020
Approximating maximum integral multiflows on bounded genus graphs
We devise the first constant-factor approximation algorithm for finding ...
research
∙
01/06/2020
An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
We devise a constant-factor approximation algorithm for the maximization...
research
∙
04/08/2019
On popularity-based random matching markets
Stable matching in a community consisting of N men and N women is a clas...
research
∙
11/05/2018
How to aggregate Top-lists: Score based approximation schemes
We study the aggregation of partial rankings and give a PTAS for TOP-AGG...
research
∙
06/21/2018
Instance-Optimality in the Noisy Value-and Comparison-Model --- Accept, Accept, Strong Accept: Which Papers get in?
Motivated by crowdsourced computation, peer-grading, and recommendation ...
research
∙
08/25/2009