The k-means for lines is a set of k centers (points) that minimizes the sum of squared distances to a given set of n lines in R^d. This is a straightforward generalization of the k-means problem where the input is a set of n points. Related problems minimize sum of (non-squared) distances, other norms, m-estimators or ignore the t farthest points (outliers) from the k centers. We suggest the first provable PTAS algorithms for these problems that compute (1+epsilon)-approximation in time O(n\log (n)/epsilon^2) for any given epsilon \in (0, 1), and constant integers k, d, t \geq 1, including support for streaming and distributed input. Experimental results on Amazon EC2 cloud and open source are also provided.
We revisit the range sampling problem: the input is a set of points where each point is associated with a real-valued weight. The goal is to store them in a structure such that given a query range and an integer , we can extract independent random samples from the points inside the query range, where the probability of sampling a point is proportional to its weight. This line of work was initiated in 2014 by Hu, Qiao, and Tao and it was later followed up by Afshani and Wei. The first line of work mostly studied unweighted but dynamic version of the problem in one dimension whereas the second result considered the static weighted problem in one dimension as well as the unweighted problem in 3D for halfspace queries. We offer three main results and some interesting insights that were missed by the previous work: We show that it is possible to build efficient data structures for range sampling queries if we allow the query time to hold in expectation (the first result), or obtain efficient worst-case query bounds by allowing the sampling probability to be approximately proportional to the weight (the second result). The third result is a conditional lower bound that shows essentially one of the previous two concessions is needed. For instance, for the 3D range sampling queries, the first two results give efficient data structures with near-linear space and polylogarithmic query time whereas the lower bound shows with near-linear space the worst-case query time must be close to , ignoring polylogarithmic factors. Up to our knowledge, this is the first such major gap between the expected and worst-case query time of a range searching problem.
We report the first improvement in the space-time trade-off of lower bounds for the orthogonal range searching problem in the semigroup model, since Chazelle's result from 1990. This is one of the very fundamental problems in range searching with a long history. Previously, Andrew Yao's influential result had shown that the problem is already non-trivial in one dimension~\cite{Yao-1Dlb}: using units of space, the query time must be where is the inverse Ackermann's function, a very slowly growing function. In dimensions, Bernard Chazelle~\cite{Chazelle.LB.II} proved that the query time must be where . Chazelle's lower bound is known to be tight for when space consumption is high' i.e., . We have two main results. The first is a lower bound that shows Chazelle's lower bound was not tight forlow space': we prove that we must have . Our lower bound does not close the gap to the existing data structures, however, our second result is that our analysis is tight. Thus, we believe the gap is in fact natural since lower bounds are proven for idempotent semigroups while the data structures are built for general semigroups and thus they cannot assume (and use) the properties of an idempotent semigroup. As a result, we believe to close the gap one must study lower bounds for non-idempotent semigroups or building data structures for idempotent semigroups. We develope significantly new ideas for both of our results that could be useful in pursuing either of these directions.
Carla Binucci, Giordano Da Lozzo, Emilio Di Giacomo, Walter Didimo, Tamara Mchedlidze, Maurizio Patrignani
2019-03-19
We study -page upward book embeddings (UBEs) of -graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a UBE is NP-complete for . A hardness result for this problem was previously known only for [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on . On the algorithmic side, we present polynomial-time algorithms for testing the existence of UBEs of planar -graphs with branchwidth and of plane -graphs whose faces have a special structure. These algorithms run in time and time, respectively, where is a singly-exponential function on . Moreover, on the combinatorial side, we present two notable families of plane -graphs that always admit an embedding-preserving UBE.
Motivated by an application to -constrained minimization, the maximization of set functions with {\it weak submodularity} and {\it weak supermodularity}, which we call {\it weakly modular} functions, has recently become an interesting research topic. In this paper, we make theoretical and practical contributions to this topic. On the theoretical side, we prove that it is hard to improve an existing approximation guarantee, and we also show that the problem is {\it fixed-parameter-tractable} under certain conditions. On the practical side, we prove guarantees of efficient {\it multi-stage} algorithms and confirm their advantages via experiments.
Robust mean estimation is the problem of estimating the mean of a -dimensional distribution from a list of independent samples, an -fraction of which have been arbitrarily corrupted by a malicious adversary. Recent algorithmic progress has resulted in the first polynomial-time algorithms which achieve \emph{dimension-independent} rates of error: for instance, if has covariance , in polynomial-time one may find with . However, error rates achieved by current polynomial-time algorithms, while dimension-independent, are sub-optimal in many natural settings, such as when is sub-Gaussian, or has bounded -th moments. In this work we give worst-case complexity-theoretic evidence that improving on the error rates of current polynomial-time algorithms for robust mean estimation may be computationally intractable in natural settings. We show that several natural approaches to improving error rates of current polynomial-time robust mean estimation algorithms would imply efficient algorithms for the small-set expansion problem, refuting Raghavendra and Steurer's small-set expansion hypothesis (so long as ). We also give the first direct reduction to the robust mean estimation problem, starting from a plausible but nonstandard variant of the small-set expansion problem.
Rediet Abebe, Richard Cole, Vasilis Gkatzelis, Jason D. Hartline
2019-03-19
We consider the design of randomized mechanisms for one-sided matching markets, where each agent is matched to one item and there are no monetary transfers. For this problem, we introduce and analyze the randomized partial improvement (RPI) mechanism. Unlike most of the mechanisms in this setting, RPI truthfully elicits cardinal (rather than just ordinal) preferences and produces a randomized matching where each agent's utility approximates the utility she would obtain in the Nash bargaining solution with a uniform random matching as the disagreement point. Intuitively, the RPI mechanism pretends that the agents are initially endowed with a uniform random assignment. Then, leveraging random sampling and invoking the partial allocation mechanism of Cole et al. (2013), RPI seeks to improve the agents' utility, while possibly, to disincentivize non-truthful reporting, leaving some of them with their initial endowment. To prove our approximation bounds, we also study the population monotonicity of the Nash bargaining solution in the context of matching markets, providing both upper and lower bounds which are of independent interest.
We substantially refine asymptotic logarithmic upper bounds produced by Svante Janson (2015) on the right tail of the limiting QuickSort distribution function and by Fill and Hung (2018) on the right tails of the corresponding density and of the absolute derivatives of of each order. For example, we establish an upper bound on that matches conjectured asymptotics of Knessl and Szpankowski (1999) through terms of order ; the corresponding order for the Janson (2015) bound is the lead order, . Using the refined asymptotic bounds on , we derive right-tail large deviation (LD) results for the distribution of the number of comparisons required by QuickSort that substantially sharpen the two-sided LD results of McDiarmid and Hayward (1996).
Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, Vincenzo Roselli
2019-03-18
We consider the problem of morphing between contact representations of a plane graph. In an -contact representation of a plane graph , vertices are realized by internally disjoint elements from a family of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in . In a morph between two -contact representations we insist that at each time step (continuously throughout the morph) we have an -contact representation. We focus on the case when is the family of triangles in that are the lower-right half of axis-parallel rectangles. Such RT-representations exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We study piecewise linear morphs, where each step is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. We provide a polynomial-time algorithm that decides whether there is a piecewise linear morph between two RT-representations of an -vertex plane triangulation, and, if so, computes a morph with linear morphs. As a direct consequence, we obtain that for -connected plane triangulations there is a morph between every pair of RT-representations where the ``top-most'' triangle in both representations corresponds to the same vertex. This shows that the realization space of such RT-representations of any -connected plane triangulation forms a connected set.
We give a fully polynomial-time approximation scheme (FPTAS) to count the number of independent sets on almost every -regular bipartite graph if . In the weighted case, for all sufficiently large integers and weight parameters , we also obtain an FPTAS on almost every -regular bipartite graph. Our technique is based on the recent work of Jenssen, Keevash and Perkins (SODA, 2019) and we also apply it to confirm an open question raised there: For all and sufficiently large integers , there is an FPTAS to count the number of -colorings on almost every -regular bipartite graph.
Data Structures And Algorithms | 2019-03-21 | Ecency
