Alan Roytman

STOC Conference 2018 Conference Paper

Fast fencing

• Mikkel Abrahamsen
• Anna Adamaszek
• Karl Bringmann
• Vincent Cohen-Addad
• Mehran Mehr
• Eva Rotenberg
• Alan Roytman
• Mikkel Thorup

We consider very natural ”fence enclosure” problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set S of n points in the plane, we aim at finding a set of closed curves such that (1) each point is enclosed by a curve and (2) the total length of the curves is minimized. We consider two main variants. In the first variant, we pay a unit cost per curve in addition to the total length of the curves. An equivalent formulation of this version is that we have to enclose n unit disks, paying only the total length of the enclosing curves. In the other variant, we are allowed to use at most k closed curves and pay no cost per curve. For the variant with at most k closed curves,we present an algorithm that is polynomialin both n and k . For the variant with unit cost per curve, or unit disks, we presenta near-linear time algorithm. Capoyleas, Rote, and Woeginger solved the problem with at most k curves in n O ( k ) time. Arkin, Khuller, and Mitchell used this to solve the unit cost per curve version in exponential time. At the time, they conjectured that the problem with k curves is NP-hard for general k . Our polynomial time algorithm refutes this unless P equals NP.

SODA Conference 2018 Conference Paper

The Bane of Low-Dimensionality Clustering

• Vincent Cohen-Addad
• Arnaud de Mesmay
• Eva Rotenberg
• Alan Roytman

In this paper, we give a conditional lower bound of n Ω( k ) on running time for the classic k -median and k -means clustering objectives (where n is the size of the input), even in low-dimensional Euclidean space of dimension four, assuming the Exponential Time Hypothesis (ETH). We also consider k -median (and k -means) with penalties where each point need not be assigned to a center, in which case it must pay a penalty, and extend our lower bound to at least three-dimensional Euclidean space. This stands in stark contrast to many other geometric problems such as the traveling salesman problem, or computing an independent set of unit spheres. While these problems benefit from the so-called (limited) blessing of dimensionality, as they can be solved in time n O ( k 1-1/ d ) or 2 n 1-1/ d in d dimensions, our work shows that widely-used clustering objectives have a lower bound of n Ω( k ), even in dimension four. We complete the picture by considering the two-dimensional case: we show that there is no algorithm that solves the penalized version in time less than, and provide a matching upper bound of. The main tool we use to establish these lower bounds is the placement of points on the moment curve, which takes its inspiration from constructions of point sets yielding Delaunay complexes of high complexity.

SODA Conference 2017 Conference Paper

Online Lower Bounds via Duality

• Yossi Azar
• Ilan Reuven Cohen
• Alan Roytman

In this paper, we exploit linear programming duality in the online setting, where input arrives on the fly, from the unique perspective of designing lower bounds (i. e. , hardness results) on the competitive ratio. In particular, we provide a systematic method (as opposed to ad hoc case analysis that is typically done) for obtaining online deterministic and randomized lower bounds on the competitive ratio for a wide variety of problems. We show the usefulness of our approach by providing new, tight hardness results for three diverse online problems: the Vector Bin Packing problem, Ad-auctions (and various online matching problems), and the Capital Investment problem. Our methods are sufficiently general that they can also be used to reconstruct existing lower bounds. Our approach is in stark contrast to previous works, which exploit linear programming duality to obtain positive results, often via the useful primal- dual scheme. We design a general recipe with the opposite aim of obtaining negative results via duality. The general idea behind our approach is to construct a parameterized family of primal linear programs based on a candidate collection of input sequences for proving the lower bound, where the objective function corresponds to optimizing the competitive ratio. Solving the parameterized family of primal linear programs optimally would yield a valid lower bound, but is a challenging task and limits the tools that can be applied, since analysis must be done precisely and exact optimality needs to be proved. To this end, we consider the corresponding parameterized family of dual linear programs and provide feasible solutions, where the objective function yields a lower bound on the competitive ratio. This opens up additional doors for analysis, including some of the techniques we employ (e. g. , continuous analysis, differential equations, etc.), as we need not be so careful about exact optimality. We are confident that our methods can be successfully applied to produce many more lower bounds for a wide array of online problems.

SODA Conference 2016 Conference Paper

Packing Small Vectors

• Yossi Azar
• Ilan Reuven Cohen
• Amos Fiat
• Alan Roytman

Online d -dimensional vector packing models many settings such as minimizing resources in data centers where jobs have multiple resource requirements (CPU, Memory, etc.). However, no online d -dimensional vector packing algorithm can achieve a competitive ratio better than d. Fortunately, in many natural applications, vectors are relatively small, and thus the lower bound does not hold. For sufficiently small vectors, an O (log d )-competitive algorithm was known. We improve this to a constant competitive ratio, arbitrarily close to e ≈ 2. 718, given that vectors are sufficiently small. We give improved results for the two dimensional case. For arbitrarily small vectors, the First Fit algorithm for two dimensional vector packing is no better than 2-competitive. We present a natural family of First Fit variants, and for optimized parameters get a competitive ratio ≈ 1. 48 for sufficiently small vectors. We improve upon the 1. 48 competitive ratio – not via a First Fit variant – and give a competitive ratio arbitrarily close to 4/3 for packing small, two dimensional vectors. We show that no algorithm can achieve better than a 4/3 competitive ratio for two dimensional vectors, even if one allows the algorithm to split vectors among arbitrarily many bins.

SODA Conference 2011 Conference Paper

Streaming k-means on Well-Clusterable Data

• Vladimir Braverman
• Adam Meyerson
• Rafail Ostrovsky
• Alan Roytman
• Michael Shindler
• Brian Tagiku