research
∙
09/18/2023
Maintaining Matroid Intersections Online
Maintaining a maximum bipartite matching online while minimizing recours...
share
research
∙
12/13/2022
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP
We show that the max entropy algorithm can be derandomized (with respect...
research
∙
11/24/2021
Matroid Partition Property and the Secretary Problem
A matroid ℳ on a set E of elements has the α-partition property, for som...
research
∙
01/15/2021
An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem
We give a randomized 1+√(8ln k/k)-approximation algorithm for the minimu...
research
∙
11/18/2020
Non-Adaptive Matroid Prophet Inequalities
We investigate non-adaptive algorithms for matroid prophet inequalities....
research
∙
09/29/2020
Competition Alleviates Present Bias in Task Completion
We build upon recent work [Kleinberg and Oren, 2014, Kleinberg et al., 2...
research
∙
07/02/2020
A (Slightly) Improved Approximation Algorithm for Metric TSP
For some ϵ > 10^-36 we give a 3/2-ϵ approximation algorithm for metric T...
research
∙
03/20/2019
Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue
We study combinatorial auctions with interdependent valuations. In such ...
research
∙
11/03/2017