Isotonic Regression via Partitioning

Algorithms are given for determining weighted isotonic regressions satisfying order constraints specified via a directed acyclic graph (DAG). For the L ₁ metric a partitioning approach is used which exploits the fact that L ₁ regression values can always be chosen to be data values. Extending this approach, algorithms for binary-valued L ₁ isotonic regression are used to find L _p isotonic regressions for 1<p<∞. Algorithms are given for trees, 2-dimensional and multidimensional orderings, and arbitrary DAGs. Algorithms are also given for L _p isotonic regression with constrained data and weight values, L ₁ regression with unweighted data, and L ₁ regression for DAGs where there are multiple data values at the vertices.     

Flying over a polyhedral terrain

We consider the problem of computing shortest paths in three-dimensions in the presence of a single-obstacle polyhedral terrain, and present a new algorithm that for any p?1, computes a (c+ε)-approximation to the Lp-shortest path above a polyhedral terrain in time and O(nlogn) space, where n is the number of vertices of the terrain, and c=²(p−1)/p. This leads to a FPTAS for the problem in L₁ metric, a -factor approximation algorithm in Euclidean space, and a 2-approximation algorithm in the general Lp metric.     

Computing the least quartile difference estimator in the plane

A common problem in linear regression is that largely aberrant values can strongly influence the results. The least quartile difference (LQD) regression estimator is highly robust, since it can resist up to almost 50% largely deviant data values without becoming extremely biased. Additionally, it shows good behavior on Gaussian data—in contrast to many other robust regression methods. However, the LQD is not widely used yet due to the high computational effort needed when using common algorithms. It is shown that it is possible to compute the LQD estimator for n bivariate data points in expected running time O(n²logn) or deterministic running time . Additionally, two easy to implement algorithms with slightly inferior time bounds are presented. All of these algorithms are also applicable to least quantile of squares and least median of squares regression through the origin, improving the known time bounds to expected time O(nlogn) and deterministic time . The proposed algorithms improve on known results of existing LQD algorithms and hence increase the practical relevance of the LQD estimator.     

Improved deterministic approximation algorithms for Max TSP

We present an O(n³)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically , where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n³)-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically . Both algorithms improve on the previous bests.     

How much precision is needed to compare two sums of square roots of integers?

In this paper, we investigate the problem of the minimum nonzero difference between two sums of square roots of integers. Let r(n,k) be the minimum positive value of where ai and bi are integers not larger than integer n. We prove by an explicit construction that r(n,k)=O(n−2k+3/2) for fixed k and any n. Our result implies that in order to compare two sums of k square roots of integers with at most d digits per integer, one might need precision of as many as digits. We also prove that this bound is optimal for a wide range of integers, i.e., r(n,k)=Θ(n−2k+3/2) for fixed k and for those integers in the form of and , where n^′ is any integer satisfied the form and i is any integer in [0,k−1]. We finally show that for k=2 and any n, this bound is also optimal, i.e., r(n,2)=Θ(n−7/2).     

An improved algorithm for finding a length-constrained maximum-density subtree in a tree

Given a tree T with weight and length on each edge, as well as a lower bound L and an upper bound U, the so-called length-constrained maximum-density subtree problem is to find a maximum-density subtree in T such that the length of this subtree is between L and U. In this study, we present an algorithm that runs in O(nUlogn) time for the case when the edge lengths are positive integers, where n is the number of nodes in T, which is an improvement over the previous algorithms when U=Ω(logn). In addition, we show that the time complexity of our algorithm can be reduced to , when the edge lengths being considered are uniform.     

Trading uninitialized space for time

The design of efficient graph algorithms usually precludes the test of edge existence, because an efficient support of that operation already requires time for the initialization of an adjacency-matrix representation. We describe an alternative representation of static directed graphs taking Θ(n+m) initialization time and using Θ(n²) space, which supports the efficient implementation of all usual operations on static graphs. The sparse graph representation allows the design of efficient graph algorithms using both iteration over all vertices adjacent with a given vertex and edge-existence operations, although at the expense of additional (uninitialized) space which may, nevertheless, be used for other purposes. To the best of our knowledge, the representation leads to the first graph algorithms with the disconcerting property that the time complexity is better than the space complexity.     

A note on exact distance labeling

We show that the vertices of an edge-weighted undirected graph can be labeled with labels of size O(n) such that the exact distance between any two vertices can be inferred from their labels alone in time. This improves the previous best exact distance labeling scheme that also requires O(n)-sized labels but time to compute the distance. Our scheme is almost optimal as exact distance labeling is known to require labels of length Ω(n).     

An approximation ratio for biclustering

The problem of biclustering consists of the simultaneous clustering of rows and columns of a matrix such that each of the submatrices induced by a pair of row and column clusters is as uniform as possible. In this paper we approximate the optimal biclustering by applying one-way clustering algorithms independently on the rows and on the columns of the input matrix. We show that such a solution yields a worst-case approximation ratio of under L₁-norm for 0-1 valued matrices, and of 2 under L₂-norm for real valued matrices.     

Alphabetic coding with exponential costs

This note considers an alphabetic binary tree formulation in a family of nonlinear problems. An application of this family occurs when a random outcome needs to be determined via alphabetically ordered search within a stochastic time window. Rather than finding a decision tree minimizing , this variant involves minimizing for a given a∈(0,1). Herein a dynamic programming algorithm finds the optimal solution in O(n³) time and O(n²) space; methods traditionally used to improve the speed of optimizations in related problems, such as the Hu-Tucker procedure, fail for this problem. This note thus also introduces two algorithms which can find a suboptimal solution in linear time (for one) or O(nlogn) time (for the other), with associated redundancy bounds guaranteeing their coding efficiency.     

Optimal per-edge processing times in the semi-streaming model

We present semi-streaming algorithms for basic graph problems that have optimal per-edge processing times and therefore surpass all previous semi-streaming algorithms for these tasks. The semi-streaming model, which is appropriate when dealing with massive graphs, forbids random access to the input and restricts the memory to bits.Particularly, the formerly best per-edge processing times for finding the connected components and a bipartition are O(α(n)), for determining k-vertex and k-edge connectivity O(k²n) and O(n⋅logn) respectively for any constant k and for computing a minimum spanning forest O(logn). All these time bounds we reduce to O(1).Every presented algorithm determines a solution asymptotically as fast as the best corresponding algorithm up to date in the classical RAM model, which therefore cannot convert the advantage of unlimited memory and random access into superior computing times for these problems.     

Testing juntas

We show that a boolean valued function over n variables, where each variable ranges in an arbitrary probability space, can be tested for the property of depending on only J of them using a number of queries that depends only polynomially on J and the approximation parameter ε. We present several tests that require a number of queries that is polynomial in J and linear in ε⁻¹. We show a non-adaptive test that has one-sided error, an adaptive version of it that requires fewer queries, and a non-adaptive two-sided version of the test that requires the least number of queries. We also show a two-sided non-adaptive test that applies to functions over n boolean variables, and has a more compact analysis.We then provide a lower bound of on the number of queries required for the non-adaptive testing of the above property; a lower bound of for adaptive algorithms naturally follows from this. In establishing this lower bound we also prove a result about random walks on the group Z^q₂ that may be interesting in its own right. We show that for some , the distributions of the random walk at times t and t+2 are close to each other, independently of the step distribution of the walk.We also discuss related questions. In particular, when given in advance a known J-junta function , we show how to test a function for the property of being identical to up to a permutation of the variables, in a number of queries that is polynomial in J and ε⁻¹.     

On domination number of Cartesian product of directed cycles

Let γ(G) denote the domination number of a digraph G and let Cm□Cn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In this paper, we determine the exact values: γ(C₂□Cn)=n; γ(C₃□Cn)=n if , otherwise, γ(C₃□Cn)=n+1; if , otherwise, .     

On generalized middle-level problem

Let be the subgraph of the hypercube Q_n induced by levels between k and n-k, where n?2k+1 is odd. The well-known middle-level conjecture asserts that is Hamiltonian for all k?1. We study this problem in for fixed k. It is known that and are Hamiltonian for all odd n?3. In this paper we prove that also is Hamiltonian for all odd n?5, and we conjecture that is Hamiltonian for every k?0 and every odd n?2k+1.     

Reviewing bounds on the circuit size of the hardest functions

In this paper we review the known bounds for L(n), the circuit size complexity of the hardest Boolean function on n input bits. The best known bounds appear to be