The Implicit Hitting Set (HS) approach has shown very effective for MaxSAT solving. However, only preliminary promising results have been obtained for the very similar Weighted CSP framework. In this paper we contribute towards both a better theoretical understanding of the HS approach and a more effective HS-based solvers for WCSP. First, we bound the minimum number of iterations of HS thanks to what we call distinguished cores. Then, we show a source of inefficiency by introducing two simple problems where HS is unfeasible. Next, we propose two reformulation methods that merge cost-functions to overcome the problem. We provide a theoretical analysis that quantifies the magnitude of the improvement of each method with respect to the number of iterations of the algorithm. In particular, we show that the reformulations can bring an exponential number of iterations down to a constant number in our working examples. Finally, we complement our theoretical analysis with two sets of experiments. First, we show that our results are aligned with real executions. Second, and most importantly, we conduct experiments on typical benchmark problems and show that cost-function merging may be heuristically applied and it may accelerate HS algorithms by several orders of magnitude. In some cases, it even outperforms state-of-the-art solvers.

Several recent papers in the literature have addressed the analysis of the cost P_{n,q} of partial match search for a given fixed query q - that has s out of K specified coordinates - in different multidimensional data structures. Indeed, detailed asymptotic estimates for the main term in the expected cost P_{n,q} = E {P_{n,q}} in standard and relaxed K-d trees are known (for any dimension K and any number s of specified coordinates), as well as stronger distributional results on P_{n,q} for standard 2-d trees and 2-dimensional quadtrees. In this work we derive a precise asymptotic estimate for the main order term of P_{n,q} in quadtrees, for any values of K and s, 0 < s < K, under the assumption that the limit of P_{n,q}/n^alpha when n -> infty exists, where alpha is the exponent of n in the expected cost of a random partial match query with s specified coordinates in a random K-dimensional quadtree.

A k-cut of a graph G = (V, E) is a partition of its vertex set into k parts; the size of the k-cut is the number of edges with endpoints in distinct parts. MAX-k-CUT is the optimization problem of finding a k-cut of maximal size and the case where k = 2 (often called MAX-CUT) has attracted a lot of attention from the research community. MAX-CUT—more generally, MAX-k-CUT— is NP-hard and it appears in many applications under various disguises. In this paper, we consider the MAX-CUT problem on random connected graphs ℂ(n, m) and on Erdős-Rényi random graphs G(n, m). More specifically, we consider the distance from bipartiteness of a graph G = (V, E), the minimum number of edge deletions needed to turn it into a bipartite graph. If we denote this distance DistBip(G), the size of the MAX-CUT of a graph G = (V, E) is clearly given by |E| − DistBip(G). Fix ε > 0. For random connected graphs, we prove that asymptotically almost surely (a.a.s) (DistBip whenever m = n + O(n1−ε). For sparse random graphs we show that DistBip ( (n, m)) is a.a.s about .

Range Quickselect, a simple modification of the well-known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Range Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm.The key element appearing in the analysis of Range Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us.In particular, we have been able to carry out a precise analysis of the expected number of moves of the pth element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results.Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.

Quickselect with median-of-3 is largely used in practice and its behavior is fairly well understood. However, the following natural adaptive variant, which we call proportion-from-3 , had not been previously analyzed: “choose as pivot the smallest of the sample if the relative rank of the sought element is below 1/3, the largest if the relative rank is above 2/3, and the median if the relative rank is between 1/3 and 2/3.” We first analyze the average number of comparisons made when using proportion-from-2 and then for proportion-from-3. We also analyze ν-find, a generalization of proportion-from-3 with interval breakpoints at ν and 1-ν. We show that there exists an optimal value of ν and we also provide the range of values of ν where ν-find outperforms median-of-3. Then, we consider the average total cost of these strategies, which takes into account the cost of both comparisons and exchanges. Our results strongly suggest that a suitable implementation of ν-find could be the method of choice in a practical setting. We also study the behavior of proportion-from- s with s >3 and in particular we show that proportion-from- s -like strategies are optimal when s →∞.

In this paper, we define and study error locating arrays (ELAs), which can be used in software testing for locating faulty interactions among parameters or components in a system. We give constructions of ELAs for arbitrary strength t, based on covering arrays. We show that the number of tests given by ELAs grows as $O(\log k)$, where k is the number of parameters/components in the system, assuming other quantities (the number g of values per parameter, the strength t of faulty interactions, and the number d of faulty interactions) are bounded by a constant. We then give a series of results for the case of pairwise interactions ($t=2$). We study the computational complexity of deciding whether a graph describing the faulty pairwise interactions is “locatable.” We characterize the locatable graphs for the binary case ($g=2$). We design and analyze efficient algorithms that locate errors under certain assumptions on the structure of the faulty pairwise interactions. Under the assumption of known “safe values,” our algorithm performs a number of tests that is polynomial in $\log k$ and d, where k is the number of parameters in the system and d is an upper bound on the number of faulty pairwise interactions. For the binary alphabet case, we provide an algorithm that does not require safe values and runs in expected polynomial time in $\log k$ whenever $d\in O(\log\log k)$.

In this work we present an in-depth study of randomized relaxed K -d trees. It covers two fundamental aspects: the randomized algorithms that allow to preserve the random properties of relaxed K -d trees and the mathematical analysis of the expected performance of these algorithms. In particular, we describe randomized update algorithms for K -d trees based on the split and join algorithms of Duch et al. [1998]. We carry out an analysis of the expected cost of all these algorithms, using analytic combinatorics techniques. We show that the average cost of split and join is of the form ζ( K ) ⋅ n ϕ( K ) + o ( n ϕ( K ) ), with 1 ≤ ϕ( K ) < 1.561552813, and we give explicit formulæ for both ζ( K ) and ϕ( K ). These results on the average performance of split and join imply that the expected cost of an insertion or a deletion is Θ( n ϕ( K )−1 ) when K > 2 and Θ(log n ) for K = 2.

It is well known that the performance of quicksort can be improved by selecting the median of a sample of elements as the pivot of each partitioning stage. For large samples the partitions are better, but the amount of additional comparisons and exchanges to find the median of the sample also increases. We show in this paper that the optimal sample size to minimize the average total cost of quicksort, as a function of the size n of the current subarray size, is $a\cdot \sqrt{n} + o(\sqrt{n}\,)$. We give a closed expression for a, which depends on the selection algorithm and the costs of elementary comparisons and exchanges. Moreover, we show that selecting the medians of the samples as pivots is not the best strategy when exchanges are much more expensive than comparisons. We also apply the same ideas and techniques to the analysis of quickselect and get similar results.

In this paper, we present randomized algorithms over binary search trees such that: (a) the insertion of a set of keys, in any fixed order, into an initially empty tree always produces a random binary search tree; (b) the deletion of any key from a random binary search tree results in a random binary search tree; (c) the random choices made by the algorithms are based upon the sizes of the subtrees of the tree; this implies that we can support accesses by rank without additional storage requirements or modification of the data structures; and (d) the cost of any elementary operation, measured as the number of visited nodes, is the same as the expected cost of its standard deterministic counterpart; hence, all search and update operations have guaranteed expected cost O(log n ), but now irrespective of any assumption on the input distribution.

The average-case analysis of algorithms for binary search trees yields very different results from those obtained under the uniform distribution. The analysis itself is more complex and replaces algebraic equations by integral equations. In this work this analysis is carried out for the computation of the average size of the intersection of two binary trees. The development of this analysis involves Bessel functions that appear in the solutions of partial differential equations, and the result has an average size of $O(n^{2\sqrt 2 - 2} /\sqrt {\log n} )$, contrasting with the size $O(1)$ obtained when considering a uniform distribution.