4 papers
Matroid-Based TSP Rounding for Half-Integral Solutions
Anupam Gupta, Euiwoong Lee, Jason Li +3
We show how to round any half-integral solution to the subtour-elimination relaxation for the TSP, while losing a less-than-1.5 factor. Such a rounding algorithm was recently given…
Tolerance for colorful Tverberg partitions
Sherry Sarkar, Pablo Soberón
Tverberg's theorem bounds the number of points needed for the existence of a partition into parts whose convex hulls intersect. If the points are colored with $N…
Quantitative combinatorial geometry for concave functions
Sherry Sarkar, Alexander Xue, Pablo Soberón
We prove several exact quantitative versions of Helly's and Tverberg's theorems, which guarantee that a finite family of convex sets in has a large intersection. Our results…
Stability for Take-Away Games
Simon Rubinstein-Salzedo, Sherry Sarkar
In this paper, we study a family of take-away games called -tag, parametrized by a real number . We show that for any given , there is a half-open interval cont…