Edge ranking and searching in partial orders

We consider a problem of searching an element in a partially ordered set (poset). The goal is to find a search strategy which minimizes the number of comparisons. Ben-Asher, Farchi and Newman considered a special case where the partial order has the maximum element and the Hasse diagram is a tree (tree-like posets) and they gave an O(n⁴log³n)-time algorithm for finding an optimal search strategy for such a partial order. We show that this problem is equivalent to finding edge ranking of a simple tree corresponding to the Hasse diagram, which implies the existence of a linear-time algorithm for this problem.Then we study a more general problem, namely searching in any partial order with maximum element. We prove that such a generalization is hard, and we give an -approximate polynomial-time algorithm for this problem.     

Augmenting forests to meet odd diameter requirements

Given a graph G=(V,E) and an integer D≥1, we consider the problem of augmenting G by the smallest number of new edges so that the diameter becomes at most D. It is known that no constant approximation algorithms to this problem with an arbitrary graph G can be obtained unless P=NP. For a forest G and an odd D≥3, it was open whether the problem is approximable within a constant factor. In this paper, we give the first constant factor approximation algorithm to the problem with a forest G and an odd D; our algorithm delivers an 8-approximate solution in O(|V|³) time. We also show that a 4-approximate solution to the problem with a forest G and an odd D can be obtained in linear time if the augmented graph is additionally required to be biconnected.     

Triply-Logarithmic Parallel Upper and Lower Bounds for Minimum and Range Minima over Small Domains

We consider the problem of computing the minimum ofnvalues, and several well-known generalizations [prefix minima, range minima, and all nearest smaller values (ANSV)] for input elements drawn from the integer domain [1···s], wheres ≥ n. In this article we give simple and efficient algorithms for all of the preceding problems. These algorithms all takeO(log log log s) time using an optimal number of processors andO(ns^ε) space (for constant ε < 1) on the COMMON CRCW PRAM. The best known upper bounds for the range minima and ANSV problems were previouslyO(log log n) (using algorithms for unbounded domains). For the prefix minima and for the minimum problems, the improvement is with regard to the model of computation. We also prove a lower bound of Ω(log log n) for domain sizes = 2^{Ω(log n log log n)}. Since, forsat the lower end of this range, log log n = Ω(log log log s), this demonstrates that any algorithm running ino(log log log s) time must restrict the range ofson which it works.     

On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem

Considering an arbitrary undirected n-vertex graph with nonnegative edge weights, we seek to construct a spanning tree minimizing the sum over all vertices of the maximal weights of the incident edges. We find some particular cases of polynomial solvability and show that the minimal span whose edge weights lie in the closed interval [a, b] is a $\left( {2 - \frac{{2a}} {{a + b + 2b/(n - 2)}}} \right) $ -approximate solution, and the problem of constructing a 1.00048-approximate solution is NP-hard. We propose a heuristic polynomial algorithm and perform its a posteriori analysis.     

z-Approximations

Approximation algorithms for NP-hard optimization problems have been widely studied for over three decades. Most of these measure the quality of the solution produced by taking the ratio of the cost of the solution produced by the algorithm to the cost of an optimal solution. In certain cases, this ratio may not be very meaningful—for example, if the ratio of the worst solution to the best solution is at most some constant α, then an approximation algorithm with factor α may in fact yield the worst solution! To overcome this hurdle (among others), several authors have independently suggested the use of a different measure which we call z-approximation. An algorithm is an α z-approximation if it runs in polynomial time and produces a solution whose distance from the optimal one is at most α times the distance between the optimal solution and the worst possible solution. The results known so far about z-approximations are either of the inapproximability type or rather straightforward observations. We design polynomial time algorithms for several fundamental discrete optimization problems; in particular we obtain a z-approximation factor of for the

Full-size image

(TSP) (with no triangle inequality assumption). For the TSP this improves to . We also show that if there is a polynomial time algorithm that for any fixed ε > 0 yields an ε z-approximation then P = NP. We also present z-approximations for severa1 other problems such as

Full-size image

, and

Full-size image

.     

Complexity of fixed points, I

We study the complexity (minimal cost) of computing an s-approximation to a fixed point of a contractive function with the contractive factor q < 1. This is done for the relative error criterion in Part I and for the absolute error criterion in Part II, which is in progress. The complexity depends strongly on the dimension of the domain of functions. For the one-dimensional case we develop an optimal fixed point envelope (FPE) algorithm. The cost of the FPE algorithm with use of the relative error criterion is roughly , where c is the cost of one function evaluation. Thus, for fixed ε and q close to 1 the cost of the FPE algorithm is much smaller than the cost of the simple iteration algorithm, since the latter is roughly For the contractive functions of d variables, with d ≥ log(1/ε)/log(l/q) we show that it is impossible to essentially improve the efficiency of the simple iteration.     

Minimizing the total completion time on-line on a single machine, using restarts

We give an algorithm to minimize the total completion time on-line on a single machine, using restarts, with a competitive ratio of 3/2. The optimal competitive ratio without using restarts is 2 for deterministic algorithms and e/(e−1)≈1.582 for randomized algorithms. This is the first restarting algorithm to minimize the total completion time that is proved to be better than an algorithm that does not restart.     

A Randomized Parallel Algorithm for Planar Graph Isomorphism

We present a parallel randomized algorithm running on aCRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph (which can be computed by known algorithms inO(log² n) time withn^{1 + ε}processors, for any ε > 0). Ifnis the number of vertices, our algorithm takesO(log(n)) time with processors and with a probability of failure of 1/nat most. The algorithm needs 2 · log(m) − log(n) + O(log(n)) random bits. The number of random bits can be decreased toO(log(n)) by increasing the number of processors ton^{3/2 + ε}, for any ε > 0. Our parallel algorithm has significantly improved processor efficiency, compared to the previous logarithmic time parallel algorithm of Miller and Reif (Siam J. Comput.20(1991), 1128–1147), which requiresn⁴randomized processors orn⁵deterministic processors.     

Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs

Karloff and Zwick obtained recently an optimal 7/8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7/8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-SAT, namely MAX 4-SAT. We present a semidefinite programming relaxation of MAX 4-SAT and a new family of rounding procedures that try to cope well with clauses of various sizes. We study the potential, and the limitations, of the relaxation and of the proposed family of rounding procedures using a combination of theoretical and experimental means. We select two rounding procedures from the proposed family of rounding procedures. Using the first rounding procedure we seem to obtain an almost optimal 0.8721-approximation algorithm for MAX 4-SAT. Using the second rounding procedure we seem to obtain an optimal 7/8-approximation algorithm for satisfiable instances of MAX 4-SAT. On the other hand, we show that no rounding procedure from the family considered can be shown, using the current techniques, to yield an approximation algorithm for MAX 4-SAT whose performance guarantee for all instances of the problem is greater than 0.8724. We also show that the integrality ratio of the proposed relaxation, as a relaxation of MAX {1, 4}-SAT, is at most 0.8754.The 0.8721-approximation for MAX 4-SAT that we seem to obtain substantially improves the performance guarantees of all previous algorithms suggested for the problem. It is extremely close to being optimal as a (7/8 + ε)-approximation algorithm for MAX 4-SAT, for any fixed ε > 0, would imply that P = NP. Our investigation also indicates, however, that additional ideas are required in order to obtain optimal 7/8-approximation algorithms for MAX 4-SAT and MAX SAT.Although most of this paper deals specifically with the MAX 4-SAT problem, we believe that the new family of rounding procedures introduced and the methodology used in the design and in the analysis of the various rounding procedures considered have a much wider range of applicability.     

The homotopical reduction of a nearest neighbor random walk*

Consider a nearest neighbor random walk on a graph G and discard all the segments of its trajectory that are homotopically equivalent to a single point. We prove that if the lift of the random walk to the covering tree of G is transient, then the resulting reduced trajectories induce a Markov chain on the set of oriented edges of G. We study this chain in relation with the original random walk. As an intermediate result, we give a simple proof of the Markovian structure of the harmonic measure on trees.* Supported by Nucleus Millennium Information and Randomness ICM P01-005.     

Robust nonparametric regression estimation

In this paper we define a robust conditional location functional without requiring any moment condition. We apply the nonparametric proposals considered by C. Stone (Ann. Statist. 5 (1977), 595–645) to this functional equation in order to obtain strongly consistent, robust nonparametric estimates of the regression function. We give some examples by using nearest neighbor weights or weights based on kernel methods under no assumptions whatsoever on the probability measure of the vector (X,Y). We also derive strong convergence rates and the asymptotic distribution of the proposed estimates.     

Graphs satisfying inequality θ(G)θ(G)

In this paper, we study the edge clique cover number of squares of graphs. More specifically, we study the inequality θ(G²)θ(G) where θ(G) is the edge clique cover number of a graph G. We show that any graph G with at most θ(G) vertices satisfies the inequality. Among the graphs with more than θ(G) vertices, we find some graphs violating the inequality and show that dually chordal graphs and power-chordal graphs satisfy the inequality. Especially, we give an exact formula computing θ(T²) for a tree T.     

Selection in Monotone Matrices and Computingkth Nearest Neighbors

Anm×nmatrix =(a_{i, j}), 1≤i≤mand 1≤j≤n, is called atotally monotonematrix if for alli₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anyk≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p₁,…, p_n} ofnpoints in convex position and a vectork={k₁,…, k_n}, we also present anO(n^4/3log^c n) algorithm to compute thek_ith nearest neighbor ofp_ifor everyi≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thek_ith nearest neighbor ofp_i, for alli≤n, can be computed in timeO(n^7/5 log^c n), which also improves upon the previously best-known result.     

A Faster Deterministic Maximum Flow Algorithm

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n² log²n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(log_{m/n log n}n)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(n^ε) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n).     

A nearest neighbor sweep circle algorithm for computing discrete Voronoi tessellations

An algorithm for computing discrete, 2-dimensional, Euclidean Voronoi tessellations is presented. The algorithm combines a limiting sweep circle approach with a nearest neighbor cellular approach. It reduces the computational cost of the naïve approach while at the same time giving the Euclidean Voronoi tessellations that simple nearest neighbor algorithms are unable to produce. The algorithm is shown, through analytical methods, to produce good approximations to corresponding continuous Voronoi tessellations depending on the definition of neighbor used in the nearest neighbor step and the mesh size. The quality of different types of neighbor definitions are discussed as well as the computational cost. The algorithm is general enough to be easily extended to higher dimensions and nonuniform meshes. The analysis lays the groundwork for the computation of discrete centroidal Voronoi tessellations where some kind of numerical integration is required.     

Once edge-reinforced random walk on a tree

 We consider a nearest neighbor walk on a regular tree, with transition probabilities proportional to weights or conductances of the edges. Initially all edges have weight 1, and the weight of an edge is increased to $c > 1$ when the edge is traversed for the first time. After such a change the weight of an edge stays at $c$ forever. We show that such a walk is transient for all values of $c \ge 1$, and that the walk moves off to infinity at a linear rate. We also prove an invariance principle for the height of the walk. Received: 6 March 2001 / Revised version: 16 July 2001 / Published online: 15 March 2002     

Finding the shortest paths by node combination

By repeatedly combining the source node’s nearest neighbor, we propose a node combination (NC) method to implement the Dijkstra’s algorithm. The NC algorithm finds the shortest paths with three simple iterative steps: find the nearest neighbor of the source node, combine that node with the source node, and modify the weights on edges that connect to the nearest neighbor. The NC algorithm is more comprehensible and convenient for programming as there is no need to maintain a set with the nodes’ distances. Experimental evaluations on various networks reveal that the NC algorithm is as efficient as Dijkstra’s algorithm. As the whole process of the NC algorithm can be implemented with vectors, we also show how to find the shortest paths on a weight matrix.     

Optimization over the polyhedron determined by a submodular function on a co-intersecting family

A greedy algorithm solves the problem of maximizing a linear objective function over the polyhedron (called the submodular polyhedron) determined by a submodular function on a distributive lattice or a ring family. We generalize the problem by considering a submodular function on a co-intersecting family and give an algorithm for solving it. Here, simple-minded greedy augmentations do not work any more and some complicated augmentations with multiple exchanges are required. We can find an optimal solution by at most 1/2n(n – 1) augmentations, wheren is the number of the variables and we assume a certain oracle for computing multiple exchange capacities.     

Perturbed and non-perturbed Brownian taboo processes

In this paper we study the Brownian taboo process, which is a version of Brownian motion conditioned to stay within a finite interval, and the α-perturbed Brownian taboo process, which is an analogous version of an α-perturbed Brownian motion.We are particularly interested in the asymptotic behaviour of the supremum of the taboo process, and our main results give integral tests for upper and lower functions of the supremum as t→∞. In the Brownian case these include extensions of recent results in Lambert [4], but are proved in a quite different way.     

Improved approximation of Max-Cut on graphs of bounded degree

Let α0.87856 denote the best approximation ratio currently known for the Max-Cut problem on general graphs. We consider a semidefinite relaxation of the Max-Cut problem, round it using the random hyperplane rounding technique of Goemans and Williamson [J. ACM 42 (1995) 1115–1145], and then add a local improvement step. We show that for graphs of degree at most Δ, our algorithm achieves an approximation ratio of at least α+ε, where ε>0 is a constant that depends only on Δ. Using computer assisted analysis, we show that for graphs of maximal degree 3 our algorithm obtains an approximation ratio of at least 0.921, and for 3-regular graphs the approximation ratio is at least 0.924. We note that for the semidefinite relaxation of Max-Cut used by Goemans and Williamson the integrality gap is at least 1/0.885, even for 2-regular graphs.