The ARRIVAL problem is to decide the fate of a train moving along the edges of a directed graph, according to a simple (deterministic) pseudorandom walk. The problem is in NP∩coNP but not known to be in 𝖯. The currently best algorithms have runtime 2^Θ(n) where n is the number of vertices. This is not much better than just performing the pseudorandom walk. We develop a subexponential algorithm with runtime 2^O(√nlog n). We also give a polynomial-time algorithm if the graph is almost acyclic. Both results are derived from a new general approach to solve ARRIVAL instances.

A function f: \mathbbR^d →\mathbbR is referred to as a Sparse Additive Model (SPAM), if it is of the form f(x) = \sum_l ∈S \phi_l(x_l), where S ⊂[d], |S| ≪d. Assuming \phi_l’s and S to be unknown, the problem of estimating f from its samples has been studied extensively. In this work, we consider a generalized SPAM, allowing for second order interaction terms. For some S_1 ⊂[d], S_2 ⊂[d] \choose 2, the function f is assumed to be of the form: f(x) = \sum_p ∈S_1 \phi_p (x_p) + \sum_(l,l’) ∈S_2 \phi_l,l’ (x_l, x_l’). Assuming \phi_p, \phi_(l,l’), S_1 and S_2 to be unknown, we provide a randomized algorithm that queries f and exactly recovers S_1,S_2. Consequently, this also enables us to estimate the underlying \phi_p, \phi_l,l’. We derive sample complexity bounds for our scheme and also extend our analysis to include the situation where the queries are corrupted with noise – either stochastic, or arbitrary but bounded. Lastly, we provide simulation results on synthetic data, that validate our theoretical findings.

Random sampling is a classical tool in constrained optimization. Under favorable conditions, the optimal solution subject to a small subset of randomly chosen constraints violates only a small subset of the remaining constraints. Here we study the following variant that we call random sampling with removal: suppose that after sampling the subset, we remove a fixed number of constraints from the sample, according to an arbitrary rule. Is it still true that the optimal solution of the reduced sample violates only a small subset of the constraints? The question naturally comes up in situations where the solution subject to the sampled constraints is used as an approximate solution to the original problem. In this case, it makes sense to improve cost and volatility of the sample solution by removing some of the constraints that appear most restricting. At the same time, the approximation quality (measured in terms of violated constraints) should remain high. We study random sampling with removal in a generalized, completely abstract setting where we assign to each subset R of the constraints an arbitrary set V(R) of constraints disjoint from R; in applications, V(R) corresponds to the constraints violated by the optimal solution subject to only the constraints in R. Furthermore, our results are parametrized by the dimension d, i.e., we assume that every set R has a subset B of size at most d with the same set of violated constraints. This is the first time this generalized setting is studied. In this setting, we prove matching upper and lower bounds for the expected number of constraints violated by a random sample, after the removal of k elements. For a large range of values of k, the new upper bounds improve the previously best bounds for LP-type problems, which moreover had only been known in special cases. We show that this bound on special LP-type problems, can be derived in the much more general setting of violator spaces, and with very elementary proofs.

The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs) in dictionary form, given by n equality constraints in n+d variables, where the variables are constrained to be nonnegative. A variable x_r is called redundant, if after removing its nonnegativity constraint the LP still has the same feasible region. The time needed to solve such an LP is denoted by LP(n,d). It is easy to see that solving n+d LPs of the above size is sufficient to detect all redundancies. The currently fastest practical method is the one by Clarkson: it solves n+d linear programs, but each of them has at most s variables, where s is the number of nonredundant constraints. In the first part we show that knowing all of the finitely many dictionaries of the LP is sufficient for the purpose of redundancy detection. A dictionary is a matrix that can be thought of as an enriched encoding of a vertex in the LP. Moreover - and this is the combinatorial aspect - it is enough to know only the signs of the entries, the actual values do not matter. Concretely we show that for any variable x_r one can find a dictionary, such that its sign pattern is either a redundancy or nonredundancy certificate for x_r. In the second part we show that considering only the sign patterns of the dictionary, there is an output sensitive algorithm of running time of order d (n+d) s^{d-1} LP(s,d) + d s^{d} LP(n,d) to detect all redundancies. In the case where all constraints are in general position, the running time is of order s LP(n,d) + (n+d) LP(s,d), which is essentially the running time of the Clarkson method. Our algorithm extends naturally to a more general setting of arrangements of oriented topological hyperplane arrangements.

Given a Boolean Circuit with n inputs and n outputs, we want to decide if it represents a Unique Sink Orientation (USO). USOs are useful combinatorial objects that serve as abstraction of many relevant optimization problems. We prove that recognizing a USO is coNP-complete. However, the situation appears to be more complicated for recognizing acyclic USOs. Firstly, we give a construction to prove that there exist cyclic USOs where the smallest cycle is of superpolynomial size. This implies that the straightforward representation of a cycle (i.e. by a list of vertices) does not make up for a coNP certificate. Inspired by this fact, we investigate the connection of recognizing an acyclic USO to PSPACE and we prove that the problem is PSPACE-complete.

Random sampling is an important tool in optimization subject to finitely or infinitely many constraints. Here we are interested in obtaining solutions of low cost that violate only few constraints. Under convexity or similar favorable conditions, and assuming fixed dimension, one can indeed derive combinatorial bounds on the expected number (or probability mass) of constraints violated by the optimal solution subject to a (small) random sample of constraints. The cost of the sample solution, however, cannot be bounded combinatorially.

The list update problem is a classical online problem, with an optimal competitive ratio that is still open, known to be somewhere between 1.5 and 1.6. An algorithm with competitive ratio 1.6, the smallest known to date, is COMB, a randomized combination of BIT and the TIMESTAMP algorithm TS. This and almost all other list update algorithms, like MTF, are projective in the sense that they can be defined by looking only at any pair of list items at a time. Projectivity (also known as “list factoring”) simplifies both the description of the algorithm and its analysis, and so far seems to be the only way to define a good online algorithm for lists of arbitrary length. In this article, we characterize all projective list update algorithms and show that their competitive ratio is never smaller than 1.6 in the partial cost model. Therefore, COMB is a best possible projective algorithm in this model.

Certain geometric optimization problems, for example finding the smallest enclosing ellipse of a set of points, can be solved in linear time by simple randomized (or complicated deterministic) combinatorial algorithms. In practice, these algorithms are enhanced or replaced with heuristic variants that are faster but do not come with a theoretical runtime guarantee. In this paper, we introduce a new speed-up heuristic that can easily be integrated into the known lineartime algorithms, without decreasing their worst-case performance. The heuristic can actually be defined for every problem in the well-known abstract class of LP-type problems; its effectiveness in practice depends on whether and how fast the heuristic can be implemented for the specific problem at hand, and on whether the input distribution is favorable. We provide test results showing that for two concrete problems, the new heuristic may lead to significant speedups compared to state-of-the-art implementations that are available in the Computational Geometry Algorithms Library CGAL.

Following recent work of Clarkson, we translate the coreset framework to the problems of finding the point closest to the origin inside a polytope, finding the shortest distance between two polytopes, Perceptrons, and soft- as well as hard-margin Support Vector Machines (SVM). We prove asymptotically matching upper and lower bounds on the size of coresets, stating that µ-coresets of size (1+o(1)) E*/µ do always exist as µ-0, and that this is best possible. The crucial quantity E* is what we call the excentricity of a polytope, or a pair of polytopes. Additionally, we prove linear convergence speed of Gilbert's algorithm, one of the earliest known approximation algorithms for polytope distance, and generalize both the algorithm and the proof to the two polytope case. Interestingly, our coreset bounds also imply that we can for the first time prove matching upper and lower bounds for the sparsity of Perceptron and SVM solutions.

We prove that the RANDOM‐EDGE simplex‐algorithm requires an expected number of at most $13n/\sqrt{d}$ pivot steps on any simple d‐polytope with n vertices. This is the first nontrivial upper bound for general polytopes. We also describe a refined analysis that potentially yields much better bounds for specific classes of polytopes. As one application, we show that for combinatorial d‐cubes the trivial upper bound of $2^d$ on the performance of RANDOM‐EDGE can asymptotically be improved by the factor $1/d^{(1-\varepsilon)\log d}$ for every $\varepsilon>0$.

We develop algorithms for computing the smallest enclosing ball of a set of n balls in d-dimensional space. Unlike previous methods, we explicitly address small cases (n= d+1), derive the necessary primitive operations and show that they can efficiently be realized with rational arithmetic. An exact implementation (along with a fast For d=3, a set of 1,000,000 balls is processed in less than two seconds on a modern PC. and robust floating-point version) is available as part of the CGAL library.See http://www.cgal.org.Our algorithms are based on novel insights into the combinatorial structure of the problem. As it turns out, results for smallest enclosing balls of points do not extend as one might expect. For example, we show that Welzl's randomized linear-time algorithm for computing the ball spanned by a set of points fails to work for balls. Consequently, David White's adaptation of the method to the ball case---as the only available implementation so far it is mentioned in many link collections---is incorrect and may crash or, in the better case, produce wrong balls.In solving the small cases we may assume that the ball centers are affinely independent; in this case, the problem is surprisingly well-behaved: via a geometric transformation and suitable generalization, it fits into the combinatorial model of unique sink orientations whose rich structure has recently received considerable attention. One consequence is that Welzl's algorithm does work for small instances; moreover, there is a wide variety of pivoting methods for unique sink orientations which have the potential of being fast in practice even for high dimension.As a by-product, we show that the problem of finding the smallest enclosing ball of balls is computationally equivalent to the problem of finding the minimum-norm point in the convex hull of a set of balls.

We analyze a randomized pivoting process involving one line and n points in the plane. The process models the behavior of the Random-Edge simplex algorithm on simple polytopes with n facets in dimension n-2. We obtain a tight O(\log^2 n) bound for the expected number of pivot steps. This is the first nontrivial bound for Random-Edge which goes beyond bounds for specific polytopes. The process itself can be interpreted as a simple algorithm for certain 2-variable linear programming problems, and we prove a tight t(n) bound for its expected runtime.The combinatorial structure behind the process is a directed graph over pairs of points, with arc orientations induced by the pivot steps. We characterize the class of graphs arising from one line and n points, up to oriented matroid realizability.

It has been known for 30 years that pseudorandom number generators in the class of linear congruential generators (LCG) exhibit strong and predictable regularities.A widely used generator in this class is drand48.While the regulaxity is not problematic in most applications, I show that it can produce very misleading results in testing geometric algorithnls that involve determinant computations.By presenting scenarios where LCG behave 'nonrandom' (sometimes in a spectacular way), I want to raise awareness for possible problems with LCG and pseudorandom numbers in general.*This work was

We present a solver for quadratic programming problems, which is tuned for applications in computational geometry.The solver implements a generalization of the simplex method to quadratic programs.Unlike existing solvers, it is efficient if the problem is dense and has few variables or few constraints.The range of applications covers well-known problems like smallest enclosing ball, or polytope distance, but also linear programming problems like smallest enclosing annulus.We provide an exact implementation with only little overhead compared to pure floating-point code.Moreover, unlike all methods for these problems that were suggested (and implemented) before in computational geometry, the runtime in practice is not exponential in the dimension of the problem, which for example allows to compute smallest enclosing balls in dimensions up to 300 (beyond that, the exact arithmetic becomes the limiting factor).The solver follows the generic programming paradigm, and it will become part of the European computational geometry algorithms library CGAL.

Article Free Access Share on Random sampling in geometric optimization: new insights and applications Authors: Bernd Gärtner Institut für Theoretische Informatik, ETH Zürich, ETH Zentrum, CH-8092 Zürich, Switzerland Institut für Theoretische Informatik, ETH Zürich, ETH Zentrum, CH-8092 Zürich, SwitzerlandView Profile , Emo Welzl Institut für Theoretische Informatik, ETH Zürich, ETH Zentrum, CH-8092 Zürich, Switzerland Institut für Theoretische Informatik, ETH Zürich, ETH Zentrum, CH-8092 Zürich, SwitzerlandView Profile Authors Info & Claims SCG '00: Proceedings of the sixteenth annual symposium on Computational geometryMay 2000 Pages 91–99https://doi.org/10.1145/336154.336186Online:01 May 2000Publication History 8citation396DownloadsMetricsTotal Citations8Total Downloads396Last 12 Months11Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The problem of finding the unique closed ellipsoid of smallest volume enclosing an n-point set P in d-space (known as the Loewner-John ellipsoid of P) is an instance of convex programming and can be solved by general methods in time O(n) if the dimension is fixed. The problem-specific parts of these methods are encapsulated in primitive operations that deal with subproblems of constant size. We derive explicit formulae for the primitive operations of Welzl's randomized method in dimension d=2. Compared to previous ones, these formulae are simpler and faster to evaluate, and they only contain rational expressions, allowing for an exact solution.

An abstract optimization problem (AOP) is a triple $(H, <, \Phi)$ where H is a finite set, $< $ is a total order on $2^{H}$, and $\Phi $ is an oracle that, for given $F \subseteq G \subseteq H$, either reports that $F = \min_{<} \{ F' | F' \subseteq G\}$ or returns a set $F' \subseteq G$ with $F' < F$. Solving the problem means finding the minimum set in H. We present a randomized algorithm that solves any AOP with an expected number of at most \[ e^{2\sqrt n + O(\sqrt[4]{n}\ln n)} \] oracle calls, $n = |H|$. In contrast, any deterministic algorithm needs to make $2^{n} - 1$ oracle calls in the worst case. The algorithm is applied to the problem of finding the distance between two n-vertex (or n-facet) convex polyhedra in d-space, and the computation of the smallest ball containing n points in d-space; for both problems we give the first subexponential bounds in the arithmetic model of computation.

We investigate the behavior of randomized simplex algorithms on special linear programs. For this, we develop combinatorial models for the Klee-Minty cubes (1972) and similar linear programs with exponential decreasing paths. The analysis of two most natural randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots. Thus we disprove two bounds conjectured in the literature. At the same lime, we establish quadratic upper bounds for random pivots on the linear programs under investigation. This motivates the question whether some randomized pivot rules possibly have quadratic worst-case behavior on general linear programs.>

An abstract optimization problem (AOP) is a triple (H,>