Search

Recently it was shown how necessary and sufficient information for solving an orthogonally invariant linear approximation problem AX ≈ B with multiple right-hand sides can be revealed through the so-called core problem reduction; see [I. Hnětynková, M. Plešinger, and Z. Strakoš, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 917-931]. The total least squares (TLS) serves as an important example of such approximation problem. Solvability of TLS was discussed in the full generality in [I. Hnětynková et al., SIAM J. Matrix Anal. Appl., 32 (2011), pp. 748-770]. This theoretical study investigates solvability of core problems with multiple right-hand sides in the TLS sense. It is shown that, contrary to the single right-hand side case, a core problem with multiple right-hand sides may not have a TLS solution. Further possible internal structure of core problems is studied. Outputs of the classical TLS algorithm for the original problem AX ≈ B and for the core problem within AX ≈ B are compared. [ABSTRACT FROM AUTHOR]

We propose regularization schemes for deformable registration and efficient algorithms for their numerical approximation. We treat image registration as a variational optimal control problem. The deformation map is parametrized by its velocity. Tikhonov regularization ensures well-posedness. Our scheme augments standard smoothness regularization operators based on H¹- and H²-seminorms with a constraint on the divergence of the velocity field, which resembles variational formulations for Stokes incompressible ows. In our formulation, we invert for a stationary velocity field and a mass source map. This allows us to explicitly control the compressibility of the deformation map and by that the determinant of the deformation gradient. We also introduce a new regularization scheme that allows us to control shear. We use a globalized, preconditioned, matrix-free, reduced space (Gauss-)Newton-Krylov scheme for numerical optimization. We exploit variable elimination techniques to reduce the number of unknowns of our system; we only iterate on the reduced space of the velocity field. Our current implementation is limited to the two-dimensional case. The numerical experiments demonstrate that we can control the determinant of the deformation gradient without compromising registration quality. This additional control allows us to avoid oversmoothing of the deformation map. We also demonstrate that we can promote or penalize shear while controlling the determinant of the deformation gradient. [ABSTRACT FROM AUTHOR]

A computational method is introduced for choosing the regularization parameter for total variation (TV) regularization. A partial understanding of the properties of the method is provided by rigorously proving that the TV norms of the reconstructions converge with any choice of regularization parameter. The computational approach is based on computing reconstructions at a few different resolutions and various values of regularization parameter. The chosen parameter is the smallest one resulting in approximately discretization-invariant TV norms of the reconstructions. The method is tested with simulated and experimental X-ray tomography data and compared to the S-curve method. The results are comparable to those of the S-curve method. However, the S-curve method needs quantitative a priori information about the expected sparsity (TV norm) of the unknown, while the proposed method does not require such input parameters. [ABSTRACT FROM AUTHOR]

The ball-constrained weighted maximin dispersion problem (Pball) is to find a point in an n-dimensional Euclidean ball such that the minimum of the weighted Euclidean distance from given m points is maximized. We propose a new second-order cone programming relaxation for (Pball). Under the condition m ≤ n, (Pball) is polynomial-time solvable since the new relaxation is shown to be tight. In general, we prove that (Pball) is NP-hard. Then, we propose a new randomized approximation algorithm for solving (Pball), which provides a new approximation bound of.... [ABSTRACT FROM AUTHOR]

We describe a half-approximation algorithm, b-Suitor, for computing a b-Matching of maximum weight in a graph with weights on the edges. b-Matching is a generalization of the well-known Matching problem in graphs, where the objective is to choose a subset of M edges in the graph such that at most a specified number b(v) of edges in M are incident on each vertex v. Subject to this restriction we maximize the sum of the weights of the edges in M. We prove that the b-Suitor algorithm computes the same b-Matching as the one obtained by the Greedy algorithm for the problem. We implement the algorithm on serial and shared-memory parallel processors and compare its performance against a collection of approximation algorithms that have been proposed earlier. Our results show that the b-Suitor algorithm outperforms the Greedy and locally dominant edge algorithms by one to two orders of magnitude on a serial processor. The b-Suitor algorithm has a high degree of concurrency, and it scales well up to 240 threads on a shared-memory multiprocessor. The b-Suitor algorithm outperforms the locally dominant edge algorithm by a factor of 14 on 16 cores of an Intel Xeon multiprocessor. [ABSTRACT FROM AUTHOR]

Given an undirected graph G = (V,E), a collection {(s1, t1),..., (sk, tk)} of k pairs of its vertices, called demand pairs, and an integer c, the goal in the Edge-Disjoint Paths with Congestion problem is to connect the maximum possible number of demand pairs by paths, so that the maximum load on any edge (called edge congestion) does not exceed c. We show an efficient randomized algorithm to route Ω(OPT/poly log k) demand pairs with congestion at most 14, where OPT is the maximum number of pairs that can be simultaneously routed on edge-disjoint paths. The algorithm in fact routes Ω(OPTLP/poly log k) pairs, where OPTLP is the optimal value of the standard multicommodity flow relaxation for the problem. The best previous efficient algorithm that routed Ω(OPT/poly log n) pairs required congestion poly(log log n), and for the setting where the maximum allowed congestion is bounded by a constant c, the best previous efficient algorithms could only guarantee the routing of Ω(OPT/n1/c) pairs. We also introduce a new type of vertex sparsifier that we call an integral flow sparsifier; integral flow sparsifiers approximately preserve both fractional and integral routings. We show an algorithm that constructs such sparsifiers. [ABSTRACT FROM AUTHOR]

For bin packing, the input consists of n items with sizes s1, . . . , sn ∊ [0, 1] which have to be assigned to a minimum number of bins of size 1. The seminal Karmarkar-Karp algorithm from 1982 produces a solution with at most OPT +O(log2 OPT) bins. We provide the first improvement in over three decades and show that one can find a solution of cost OPT +O(logOPT · log logOPT) in polynomial time. This is achieved by rounding a fractional solution to the Gilmore-Gomory LP relaxation using the partial coloring method from discrepancy theory. The result is constructive via the algorithms of Bansal and Lovett-Meka. [ABSTRACT FROM AUTHOR]

In this paper we consider linear fractional systems of commensurate orders and with commensurate delays, whose characteristic equation is a polynomial in the two variables sα (0 < α < 1) and e-ST (T > 0). These systems may have single or multiple chains of poles asymptotic to the imaginary axis. Location of poles of large modulus belonging to these chains are determined by approximation and simple necessary and suffcient H∞-stability conditions are derived. [ABSTRACT FROM AUTHOR]

We present a methodology for the global sampled-data stabilization of systems with a compact absorbing set and input/measurement delays. The methodology is based on the inter-sample-predictor, observer, predictor, delay-free controller (ISP-O-P-DFC) scheme, and the stabilization is robust to perturbations of the sampling schedule. The obtained results are novel even for the delay-free case. [ABSTRACT FROM AUTHOR]

In the highway problem, we are given an n-edge path graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the associated path, when it does not exceed the budget of the driver, and zero otherwise. The goal is to choose weights so as to maximize the profit. A lot of research has been devoted to this apparently simple problem. The highway problem was shown to be strongly NP-hard only recently [K. M. Elbassioni et al., in Proceedings of the International Symposium on Algorithmic Game Theory (SAGT), 2009, pp. 275-286]. The best-known approximation is O(log n/ log log n) [I. Gamzu and D. Segev, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2010, pp. 582-593], which improves on the previous best O(log n) approximation [M.-F. Balcan and A. Blum, in Proceedings of the ACM Conference on Electronic Commerce, 2006, pp. 29-35]. Better approximations are known for a number of special cases. Finding a constant (or better!) approximation algorithm for the general case is a challenging open problem. In this paper we present a polynomial-time approximation scheme (PTAS) for the highway problem, hence greatly improving our understanding of the complexity status of this problem. Our result is based on a novel randomized dissection approach, which has some points in common with Arora's quadtree dissection for Euclidean network design [S. Arora, J. ACM, 45 (1998), pp. 753-782]. The basic idea is to enclose the highway in a bounding path, such that both the size of the bounding path and the position of the highway in it are random variables. Then we consider a recursive O(1)-ary dissection of the bounding path, in subpaths of uniform optimal weight. Since the optimal weights are unknown, we construct the dissection in a bottom-up fashion via dynamic programming, while computing the approximate solution at the same time. Our algorithm can be easily derandomized. The same basic approach also provides PTASs for two generalizations of the problem: the tollbooth problem with a constant number of leaves and the maximum-feasibility subsystem problem on interval matrices. In both cases the previous best approximation factors are polylogarithmic [I. Gamzu and D. Segev, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2010, pp. 582-593. [ABSTRACT FROM AUTHOR]

Under some weak conditions, the first-passage time of the Brownian motion to a continuous curved boundary is an almost surely finite stopping time. Its probability density function (pdf) is explicitly known only in few particular cases. Several mathematical studies proposed to approximate the pdf in a quite general framework or even to simulate this hitting time using a discrete time approximation of the Brownian motion. The authors study a new algorithm which permits one to simulate the first-passage time using an iterating procedure. The convergence rate presented in this paper suggests that the method is very efficient. [ABSTRACT FROM AUTHOR]

This paper compares the performance of penalty and Lagrange multiplier approaches for the necessary unit-length constraint in the computation of liquid crystal equilibrium configurations. Building on previous work in [SIAM J. Sci. Comput., 37 (2015), pp. S157-S176; SIAM J. Numer. Anal., 53 (2015), pp. 2226-2254], the penalty method is derived and well-posedness of the linearizations within the nonlinear iteration is discussed. In addition, the paper considers the effects of tailored trust-region methods in the context of finite-element discretizations and nested iteration for both formulations. Such methods are aimed at increasing the efficiency and robustness of each algorithm's nonlinear iterations. Three representative elastic equilibrium problems are considered to examine each method's performance. The first two configurations have analytical expressions for their exact solutions and, therefore, convergence to the true solution is considered. The third problem considers complicated boundary conditions, relevant in ongoing research, simulating surface nano-patterning. Finally, a novel multigrid scheme is introduced and tested for electrically and flexoelectrically coupled models to establish scalability for highly complicated applications. The Lagrange multiplier method is found to outperform the penalty method in a number of measures, the developed trust regions are shown to improve robustness, and nested iteration proves highly effective at reducing computational costs. [ABSTRACT FROM AUTHOR]

We develop a convex approximation for two-stage mixed-integer recourse models, and we derive an error bound for this approximation that depends on the total variations of the probability density functions of the random variables in the model. We show that the error bound converges to zero if all these total variations converge to zero. Our convex approximation is a generalization of the one in Romeijnders, van der Vlerk, and Klein Haneveld [Math. Program., to appear] restricted to totally unimodular integer recourse models. For this special case it has the best worst-case error bound possible. The error bound in this paper is the first in the general setting of mixed-integer recourse models. As main building blocks in its derivation we generalize the asymptotic periodicity results of Gomory [Linear Algebra Appl., 2 (1969), pp. 451-558] for pure integer programs to the mixed-integer case, and we use the total variation error bounds on the expectation of periodic functions derived in Romeijnders, van der Vlerk, and Klein Haneveld [Math. Program., to appear]. [ABSTRACT FROM AUTHOR]

Given a network, a set of demands, and a cost function ƒ(·), the min-cost network design problem is to route all demands with the objective of minimizing Σe ƒ(le), where le is the total traffic load under the routing. We focus on cost functions of the form ƒ(x) = σ + xα for x > 0, with ƒ (0) = 0. For α ≤1, ƒ(·) is subadditive. This case corresponds to the well-studied buy-at-bulk network design problem and admits polylogarithmic approximation and hardness. In this paper, we focus on the less-studied scenario of α > 1 with a positive start-up cost σ > 0. Now, the cost function ƒ(·) is neither subadditive nor superadditive. It aims to model a range of computing and communication devices for which doubling processing speed more than doubles their power consumption. We begin by discussing why existing routing techniques such as randomized rounding and tree-metric embedding fail to generalize directly. We then present our main contribution, which is a polylogarithmic approximation algorithm. We obtain this result by first deriving a bicriteria approximation for a related capacitated min-cost flow problem that we believe is interesting in its own right. Our approach for this problem builds upon the well-linked decomposition due to Chekuri, Khanna, and Shepherd [Proceedings of ACM STOC, ACM, New York, pp. 183-192], the construction of expanders via matchings due to Khandekar, Rao, and Vazirani [J. ACM, 56 (2009), 19], and edge-disjoint routing in well-connected graphs due to Rao and Zhou [SIAM J. Comput., 39 (2010), pp. 1856-1887]. However, we also develop new techniques that allow us to keep a handle on the total cost, which was not a concern in the aforementioned literature. [ABSTRACT FROM AUTHOR]

We study a general class of problems called F-DELETION problems. In an F-DELETION problem, we are asked whether a subset of at most k vertices can be deleted from a graph G such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We study the problem parameterized by k, using p-F-DELETION to refer to the parameterized version of the problem. We obtain a number of algorithmic results on the p-F-DELETION problem when F contains a planar graph. We give a linear vertex kernel on graphs excluding t-claw K1,t, the star with t leaves, as an induced subgraph, where t is a fixed integer and an approximation algorithm achieving an approximation ratio of O(log3/2 OPT), where OPT is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when F only contains graph θc as a minor for a fixed integer c. The graph θc consists of two vertices connected by c parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as VERTEX COVER, FEEDBACK VERTEX SET, and DIAMOND HITTING SET. The generic kernelization algorithm is based on a nontrivial application of protrusion techniques, previously used only for problems on topological graph classes. [ABSTRACT FROM AUTHOR]

Our goal is to show tight bounds on the running time of algorithms for scheduling and packing problems. To prove lower bounds, we investigate implications of the exponential time hypothesis on such algorithms. For exact algorithms we consider the dependence of the running time on the number n of items (for packing) or jobs (for scheduling). We prove a lower bound of 2o(n) x ∥I∥O(n), where ∥I∥ denotes the encoding length of the instance, for several of these problems, including SUBSETSUM, KNAPSACK, BINPACKING, , and . We also develop an algorithmic framework that is able to solve a large number of scheduling and packing problems in time 2o(n) x ∑I∑O(n). Finally, we consider approximation schemes. We show that there is no polynomial time approximation scheme for MULTIPLEKNAPSACK (MKS) and 2D-KNAPSACK with running time 2o(1/ε) x ∑I∑O(n) and no(1/ε) x ∑I∑O(n), respectively. [ABSTRACT FROM AUTHOR]

We address an important research area in stochastic multiscale modeling, namely, the propagation of uncertainty across heterogeneous domains characterized by partially correlated processes with vastly different correlation lengths. This class of problems arises very often when computing stochastic PDEs and particle models with stochastic/stochastic domain interaction but also with stochastic/deterministic coupling. The domains may be fully embedded, adjacent, or partially overlapping. The fundamental open question we address is the construction of proper transmission boundary conditions that preserve global statistical properties of the solution across different subdomains. Often, the codes that model different parts of the domains are black box and hence a domain decomposition technique is required. No rigorous theory or even effective empirical algorithms have yet been developed for this purpose, although interfaces defined in terms of functionals of random fields (e.g., multipoint cumulants) can overcome the computationally prohibitive problem of preserving sample-path continuity across domains. The key idea of the different methods we propose relies on combining local reduced-order representations of random fields with multilevel domain decomposition. Specifically, we propose two new algorithms: The first one enforces the continuity of the conditional mean and variance of the solution across adjacent subdomains by using Schwarz iterations. The second algorithm is based on PDE-constrained multiobjective optimization, and it allows us to set more general interface conditions. The effectiveness of these new algorithms is demonstrated in numerical examples involving elliptic problems with random diffusion coefficients, stochastically advected scalar fields, and nonlinear advection-reaction problems with random reaction rates. [ABSTRACT FROM AUTHOR]

Weighted geometric set-cover problems arise naturally in several geometric and nongeometric settings (e.g., the breakthrough of Bansal and Pruhs [Proceedings of FOCS, 2010, pp. 407-414] reduces a wide class of machine scheduling problems to weighted geometric set cover). More than two decades of research has succeeded in settling the (1 + ∈)-approximability status for most geometric set-cover problems, except for some basic scenarios which are still lacking. One is that of weighted disks in the plane for which, after a series of papers, Varadarajan [Proceedings of STOC'10, 2010, pp. 641-648] presented a clever quasi-sampling technique, which together with improvements by Chan et al. [Proceedings of SODA, 2012, pp. 1576-1585], yielded an O(1)-approximation algorithm. Even for the unweighted case, a polynomial time approximation scheme (PTAS) for a fundamental class of objects called pseudodisks (which includes halfspaces, disks, unit-height rectangles, translates of convex sets, etc.) is currently unknown. Another fundamental case is weighted halfspaces in R³, for which a PTAS is currently lacking. In this paper, we present a quasi PTAS (QPTAS) for all these remaining problems. Our results are based on the separator framework of Adamaszek and Wiese [Proceedings of FOCS, 2013, pp. 400-409; Proceedings of SODA, 2014, pp. 645-656], who recently obtained a QPTAS for a weighted independent set of polygonal regions. This rules out the possibility that these problems are APX-hard, assuming NP ... DTIME(2polylog(n)). Together with the recent work of Chan and Grant [Comput. Geom., 47 (2014), pp. 112-124], this settles the APX-hardness status for all natural geometric set-cover problems. [ABSTRACT FROM AUTHOR]

In a variety of applications it is important to extract information from a probability measure μ on an infinite dimensional space. Examples include the Bayesian approach to inverse problems and (possibly conditioned) continuous time Markov processes. It may then be of interest tofind a measure v, from within a simple class of measures, which approximates μ. This problem is studied in the case where the Kullback-Leibler divergence is employed to measure the quality of the approximation. A calculus of variations viewpoint is adopted, and the particular case where v is chosen from the set of Gaussian measures is studied in detail. Basic existence and uniqueness theorems are established, together with properties of minimizing sequences. Furthermore, parameterization of the class of Gaussians through the mean and inverse covariance is introduced, the need for regularization is explained, and a regularized minimization is studied in detail. The calculus of variations framework resulting from this work provides the appropriate underpinning for computational algorithms. [ABSTRACT FROM AUTHOR]

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. We show a dichotomy for the size of the smallest identifying code in classes of graphs closed under induced subgraphs. Our dichotomy is derived from the VC-dimension of the considered class C, that is, the maximum VCdimension over the hypergraphs formed by the closed neighborhoods of elements of C. We show that hereditary classes with infinite VC-dimension have infinitely many graphs with an identifying code of size logarithmic in the number of vertices, while classes with finite VC-dimension have a polynomial lower bound. We then turn to approximation algorithms. We show that Min Id Code (the problem of finding a smallest identifying code in a given graph from some class C) is log-APX-hard for any hereditary class of infinite VC-dimension. For hereditary classes of finite VC-dimension, the only known previous results show that we can approximate Min Id Code within a constant factor in some particular classes, e.g., line graphs, planar graphs, and unit interval graphs. We prove that Min Id Code can be approximate within a factor 6 for interval graphs. In contrast, we show that Min Id Code on C4-free bipartite graphs (a class of finite VC-dimension) cannot be approximated to within a factor of c log(|V |) for some c > 0. [ABSTRACT FROM AUTHOR]

We consider the Unconstrained Submodular Maximization problem in which we are given a nonnegative submodular function f : 2N → ℝ+, and the objective is to find a subset S ⊆ N maximizing f(S). This is one of the most basic submodular optimization problems, having a wide range of applications. Some well-known problems captured by Unconstrained Submodular Maximization include Max-Cut, Max-DiCut, and variants of Max-SAT and maximum facility location. We present a simple randomized linear time algorithm achieving a tight approximation guarantee of 1/2, thus matching the known hardness result of Feige, Mirrokni, and Vondrák [SIAM J. Comput., 40 (2011), pp. 1133-1153]. Our algorithm is based on an adaptation of the greedy approach which exploits certain symmetry properties of the problem. [ABSTRACT FROM AUTHOR]

We study the metric s-t path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875-886] improved on the long-standing 5/3-approximation factor and presented an algorithm that achieves an approximation factor of 1+√5/2 ≈ 1.61803. Later, Sebô [Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization, 2013, pp. 362-374] further improved the approximation factor to 8/5. We present a simple, self-contained analysis that unifies both results; our main contribution is a unified correction vector. Additionally, we compare two different linear programming (LP) relaxations of the s-t path TSP, namely, the path version of the Held--Karp LP relaxation for the TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum cost of integral solutions of the two LPs are within a factor of 3/2 of each other. Furthermore, we prove that a half-integral solution of the stronger LP relaxation of cost c can be rounded to an integral solution of cost at most 3/2c. Finally, we give an example that presents obstructions to two natural methods that aim for an approximation factor of 3/2. [ABSTRACT FROM AUTHOR]

We investigate the classes of functions whose minimization diagrams can be approximated efficiently in Rd. We present a general framework and a data-structure that can be used to approximate the minimization diagram of such functions. The resulting data-structure has near linear size and can answer queries in logarithmic time. Applications include approximating the Voronoi diagram of multiplicatively weighted points, but the new technique also works for more general distance functions. For example, we get such data-structures for metrics induced by convex bodies, and the nearest furthest-neighbor distance to a set of point sets. Interestingly, our framework also works for distance functions that do not obey the triangle inequality. For many of these functions no near linear size approximation was known before. [ABSTRACT FROM AUTHOR]

We give a lower bound on the iteration complexity of a natural class of Lagrangianrelaxation algorithms for approximately solving packing/covering linear programs. We show that, given an input with m random 0/1-constraints on n variables, with high probability, any such algorithm requires Ω(ρ log(m)/ϵ2) iterations to compute a (1 + ϵ)-approximate solution, where ρ is the width of the input. The bound is tight for a range of the parameters (m, n, ρ, ϵ). The algorithms in the class include Dantzig-Wolfe decomposition, Benders' decomposition, Lagrangian relaxation as developed by Held and Karp for lower-bounding TSP, and many others (e.g., those by Plotkin, Shmoys, and Tardos and Grigoriadis and Khachiyan). To prove the bound, we use a discrepancy argument to show an analogous lower bound on the support size of (1 + ϵ)-approximate mixed strategies for random two-player zero-sum 0/1-matrix games. [ABSTRACT FROM AUTHOR]

Almost sure convergence rates for linear algorithms hk+1 = hk + 1/kχ (bk - Akhk) are studied, where χ ∊ (0, 1), {Ak}∞ k=1 are symmetric, positive semidefinite random matrices and {bk}∞ k=1 are random vectors. It is shown that nγ hn - A-1b → 0 a.s. for the γ ∊ [0, χ), positive definite A and vector b such that 1/nχ-γ ∑n k=1(Ak -A) → 0 and 1/nχ-γ ∑n k=1(bk -b) → 0 a.s. When χ - γ ∊ (1/2 , 1), these assumptions are implied by the Marcinkiewicz strong law of large numbers, which allows the {Ak} and {bk} to have heavy tails, long-range dependence, or both. Finally, corroborating experimental outcomes and decreasing-gain design considerations are provided. [ABSTRACT FROM AUTHOR]

We study a basic resource allocation problem that arises in cloud computing environments. The physical network of the cloud is represented as a graph with vertices representing servers and edges corresponding to communication links. A workload is a set of processes with processing requirements and mutual communication requirements. The workloads arrive and depart over time, and the resource allocator must map each workload upon arrival to the physical network. We consider the objective of minimizing the congestion. We show that solving a subproblem (SingleMap) about mapping a single workload to the physical graph essentially suffices for solving the general problem. In particular, an α-approximation algorithm for SingleMap gives an O(α log nD) competitive algorithm for the general problem, where n is the number of nodes in the physical network and D is the maximum to minimum workload duration ratio. We then consider the SingleMap problem for two natural classes of workloads, namely depth-d trees and complete-graph workloads. For depth-d trees, we give an nO(d) time O(d2 log(nd))-approximation algorithm based on a strong LP relaxation inspired by the Sherali-Adams hierarchy. For complete graphs, we give a polylogarithmic approximation algorithm using Räcke decompositions [ABSTRACT FROM AUTHOR]

We propose a computationally efficient fully polynomial-time approximation scheme (FPTAS) to compute an approximation with arbitrary precision of the value function of convex stochastic dynamic programs, using the technique of $K$-approximation sets and functions introduced by Halman et al. [Math. Oper. Res., 34, (2009), pp. 674--685]. This paper deals with the convex case only, and it has the following contributions. First, we improve on the worst-case running time given by Halman et al. Second, we design and implement an FPTAS with excellent computational performance and show that it is faster than an exact algorithm even for small problem instances and small approximation factors, becoming orders of magnitude faster as the problem size increases. Third, we show that with careful algorithm design, the errors introduced by floating point computations can be bounded, so that we can provide a guarantee on the approximation factor over an exact infinite-precision solution. We provide an extensive computational evaluation based on randomly generated problem instances coming from applications in supply chain management and finance. The running time of the FPTAS is both theoretically and experimentally linear in the size of the uncertainty set. [ABSTRACT FROM AUTHOR]

Trevisan [SIAM J. Comput., 41 (2012), pp. 1769-1786] presented an algorithm for Max-Cut based on spectral partitioning techniques. This is the first algorithm for Max-Cut with an approximation guarantee strictly larger than 1/2 that is not based on semidefinite programming. Trevisan showed that its approximation ratio is of at least 0.531. In this paper we improve this bound up to 0.614247. We also define and extend this result for the more general maximum colored cut problem. [ABSTRACT FROM AUTHOR]

Many scientific and engineering applications feature nonsmooth convex minimization problems over convex sets. In this paper, we address an important instance of this broad class where we assume that the nonsmooth objective is equipped with a tractable proximity operator and that the convex constraint set affords a self-concordant barrier. We provide a new joint treatment of proximal and self-concordant barrier concepts and illustrate that such problems can be efficiently solved, without the need of lifting the problem dimensions, as in disciplined convex optimization approach. We propose an inexact path-following algorithmic framework and theoretically characterize the worst-case analytical complexity of this framework when the proximal subproblems are solved inexactly. To show the merits of our framework, we apply its instances to both synthetic and real-world applications, where it shows advantages over standard interior point methods. As a byproduct, we describe how our framework can obtain points on the Pareto frontier of regularized problems with self-concordant objectives in a tuning free fashion. [ABSTRACT FROM AUTHOR]

We consider the problem of maximizing a nonnegative submodular set function f : 2N → R+ over a ground set N subject to a variety of packing-type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when f may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension F of f over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize F over a downward-closed polytope P described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints or a matroid polytope. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when f is nonmonotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via linear programming duality we show that a contention resolution scheme for a constraint is related to the correlation gap of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications. [ABSTRACT FROM AUTHOR]

In this note, we prove that all cop-win graphs G in the game in which the robber and the cop move at different speeds s and s' with s' < s, are < δ-hyperbolic with δ = O(s²). We also show that the dependency between S and s is linear if s - s' = Ω(s) and G obeys a slightly stronger condition. This solves an open question from the paper [J. Chalopin et al., SIAM J. Discrete Math., 25 (2011), pp. 333-359]. Since any δ-hyperbolic graph is cop-win for s = 2r and s' = r + 2δ for any r > 0, this establishes a new--game-theoretical--characterization of Gromov hyperbolicity. We also show that for weakly modular graphs the dependency between δ and s is linear for any s' < s. Using these results, we describe a simple constant-factor approximation of the hyperbolicity δ of a graph on n vertices in O(n²) time when the graph is given by its distance matrix. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a simple graph of maximum degree Δ. The edges of G can be colored with at most Δ + 1 colors by Vizing's theorem. We study lower bounds on the size of subgraphs of G that can be colored with A colors. Vizing's theorem gives a bound of Δ/Δ + 1 |E|. This is known to be tight for cliques κΔ + 1 when Δ is even. However, for Δ = 3 it was improved to 26/31 |E| by Albertson and Haas [Discrete Math., 148 (1996), pp. 1-7] and later to 6/7|E| by Rizzi [Discrete Math., 309 (2009), pp. 4166-4170]. It is tight for B3, the graph isomorphic to a K4 with one edge subdivided. We improve previously known bounds for Δ ∈ {3,..., 7}, under the assumption that for Δ = 3,4,6, graph G is not isomorphic to B3, K5, and K7, respectively. For Δ ≥ 4 these are the first results which improve over the Vizing's bound. We also show a new bound for subcubic multigraphs not isomorphic to K3 with one edge doubled. In the second part, we give approximation algorithms for the maximum κ-edge-colorable subgraph problem, where given a graph G (without any bound on its maximum degree or other restrictions) one has to find a κ-edge-colorable subgraph with the maximum number of edges. In particular, when G is simple for κ = 3, 4, 5, 6, 7 we obtain approximation ratios of 13/15, 9/11, 19/22, 23/27, and 22/25, respectively. We also present a 7/9-approximation for κ = 3 when G is a multigraph. The approximation algorithms follow from a new general framework that can be used for any value of κ. [ABSTRACT FROM AUTHOR]

The c-pumpkin is the graph with two vertices linked by c ≥ 1 parallel edges. A c-pumpkin-model in a graph G is a pair {A, B} of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on hitting and packing c-pumpkin-models in a given graph in the realm of approximation algorithms and parameterized algorithms. We give a fixed-parameter tractable (FPT) algorithm running in time 2...(κ)(n...(1) deciding, for any fixed c ≥ 1, whether all c-pumpkin-models can be hit by at most k vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex SET, which correspond to the cases c = 1, 2 respectively. Finally, we present an ...(log n)-approximation algorithm for both the problems of hitting all c-pumpkin-models with a smallest number of vertices and packing a maximum number of vertex-disjoint c-pumpkin-models. [ABSTRACT FROM AUTHOR]

Given a capacitated graph G = (V, E) and a set of terminals K ⊆ V, how should we produce a graph H only on the terminals K so that every (multicommodity) flow between thw terminals in G could be supported in H with low congestion, and vice versa? (Such a graph H is called a flow sparsifier for G.) What if we want H to be a "simple" graph? What if we allow H to be a convex combination of simple graphs? Improving on results of Moitra [Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 3-12] and Leighton and Moitra [Proceedings of the 42nd ACM Symposium on Theory of Computing, ACM, New York, 2010, pp. 47-56], we give efficient algorithms for constructing (a) a flow sparsifier H that maintains congestion up to a factor of O(log κ/log log κ), where κ = | K |(b) a convex combination of trees over the terminals K that maintains congestion up to a factor of O(log k); (c) for a planar graph G, a convex combination of planar graphs that maintains congestion up to a constant factor. This requires us to give a new algorithm for the 0-extension problem, the first one in which the preimages of each terminal are connected in G. Moreover, this result extends to minor-closed families of graphs. Our bounds immediately imply improved approximation guarantees for several terminal-based cut and ordering problems. [ABSTRACT FROM AUTHOR]

We present a 6-approximation algorithm for the minimum-cost κ-node connected spanning subgraph problem, assuming that the number of nodes is at least κ³ (κ - 1) + κ. We apply a combinatorial preprocessing, based on the Frank--Tardos algorithm for κ-outconnectivity, to transform any input into an instance such that the iterative rounding method gives a 2-approximation guarantee. This is the first constant factor approximation algorithm even in the asymptotic setting of the problem, that is, the restriction to instances where the number of nodes is lower bounded by a function of κ. [ABSTRACT FROM AUTHOR]

In a classic optimization problem, the complete input data is assumed to be known to the algorithm. This assumption may not be true anymore in optimization problems motivated by the Internet where part of the input data is private knowledge of independent selfish agents. The goal of algorithmic mechanism design is to provide (in polynomial time) a solution to the optimization problem and a set of incentives for the agents such that disclosing the input data is a dominant strategy for the agents. In the case of NP-hard problems, the solution computed should also be a good approximation of the optimum. In this paper we focus on mechanism design for multiobjective optimization problems. In this setting we are given a main objective function and a set of secondary objectives which are modeled via budget constraints. Multiobjective optimization is a natural setting for mechanism design as many economical choices ask for a compromise between different, partially conflicting goals. The main contribution of this paper is showing that two of the main tools for the design of approximation algorithms for multiobjective optimization problems, namely, approximate Pareto sets and Lagrangian relaxation, can lead to truthful approximation schemes. By exploiting the method of approximate Pareto sets, we devise truthful deterministic and randomized multicriteria fully polynomial-time approximation schemes (FPTASs) for multiobjective optimization problems whose exact version admits a pseudopolynomial-time algorithm, as, for instance, the multibudgeted versions of minimum spanning tree, shortest path, maximum (perfect) matching,and matroid intersection. Our construction also applies to multidimensional knapsack and multiunit combinatorial auctions. Our FPTASs compute a (1+ε)-approximate solution violating each budget constraint by a factor (1+ ε). When feasible solutions induce an independence system, i.e., when subsets of feasible solutions are feasible as well, we present a PTAS (not violating any constraint), which combines the approach above with a novel monotone way to guess the heaviest elements in the optimum solution. Finally, we present a universally truthful Las Vegas PTAS for minimum spanning tree with a single budget constraint, where one wants to compute a minimum cost spanning tree whose length is at most a given value L. This result is based on the Lagrangian relaxation method, in combination with our monotone guessing step and with a random perturbation step (ensuring low expected running time). This result can be derandomized in the case of integral lengths. All the mentioned results match the best known approximation ratios, which are, however, obtained by nontruthful algorithms. [ABSTRACT FROM AUTHOR]

We present an optimal, combinatorial 1-1/e approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm [G. Calinescu et al., IPCO, Springer, Berlin, 2007, pp. 182-196] our algorithm is extremely simple and requires no rounding. It consists of the greedy algorithm followed by a local search. Both phases are run not on the actual objective function, but on a related auxiliary potential function, which is also monotone and submodular. In our previous work on maximum coverage [Y. Filmus and J. Ward, FOCS, IEEE, Piscataway, NJ, 2012, pp. 659-668], the potential function gives more weight to elements covered multiple times. We generalize this approach from coverage functions to arbitrary monotone submodular functions. When the objective function is a coverage function, both definitions of the potential function coincide. Our approach generalizes to the case where the monotone submodular function has restricted curvature. For any curvature c, we adapt our algorithm to produce a (1-e-c)/c approximation. This matches results of Vondrák [STOC, ACM, New York, 2008, pp. 67-74], who has shown that the continuous greedy algorithm produces a (1 - e-c)/c approximation when the objective function has curvature c with respect to the optimum, and proved that achieving any better approximation ratio is impossible in the value oracle model. [ABSTRACT FROM AUTHOR]

We present an approximation algorithm for the shortest descending path problem. Given a source s and a destination t on a terrain, a shortest descending path from s to t is a path of minimum Euclidean length on the terrain subject to the constraint that the height decreases monotonically as we traverse that path from s to t. Given any ε ∈ (0, 1), our algorithm returns in O(n4 log(n/ε)) time a descending path of length at most 1 + ε times the optimum. This is the first algorithm whose running time is polynomial in n and log(1/ε) and independent of the terrain geometry. [ABSTRACT FROM AUTHOR]

We study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are where the k parts need to be of equal size, and where they must separate a set of k given terminals. We consider a common generalization of these two problems, and design for it an O(√log n log k) approximation algorithm. This improves over an O(log² n) approximation for the second version due to Svitkina and Tardos [Min-max multiway cut, in APPROX-RANDOM, 2004, Springer, Berlin, 2004], and roughly O(k log n) approximation for the first version that follows from other previous work. We also give an O(1) approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the small-set expansion problem. In this problem, we are given a graph G and the goal is to find a nonempty set S ⊆ V of size |S| ≤ ρn with minimum edge expansion. We give an O(√log n log (1/ρ)) bicriteria approximation algorithm for small-set expansion in general graphs, and an improved factor of O(1) for graphs that exclude any fixed minor. [ABSTRACT FROM AUTHOR]

In the unsplittable flow problem on a path, we are given a capacitated path P and n tasks, each task having a demand, a profit, and start and end vertices. The goal is to compute a maximum profit set of tasks such that, for each edge e of P, the total demand of selected tasks that use e does not exceed the capacity of e. This is a well-studied problem that has been described under alternative names, such as resource allocation, bandwidth allocation, resource constrained scheduling, temporal knapsack, and interval packing. We present a polynomial time constant-factor approximation algorithm for this problem. This improves on the previous best known approximation ratio of O(log n). The approximation ratio of our algorithm is 7 + ∈ for any ∈ > 0. We introduce several novel algorithmic techniques, which might be of independent interest: a framework which reduces the problem to instances with a bounded range of capacities, and a new geometrically inspired dynamic program which solves to optimality a special case of the problem of finding a maximum weight independent set of rectangles. In the setting of resource augmentation, wherein the capacities can be slightly violated, we give a (2 + ∈)-approximation algorithm. In addition, we show that the problem is strongly NP-hard even if all edge capacities are equal and all demands are either 1, 2, or 3. [ABSTRACT FROM AUTHOR]

Multistate stochastic programs pose some of the more challenging optimization problems. Because such models can become rather intractable in general, it is important to design algorithms that can provide approximations which, in the long run, yield solutions that are arbitrarily close to an optimum. In this paper, we propose such a sequential sampling method which is applicable to multistage stochastic linear programs, and we refer to it as the multistage stochastic decomposition (MSD) algorithm. This algorithm represents a dynamic extension of a regularized version of stochastic decomposition (SD). While the method allows general correlation structures, specialized streamlined versions are also possible for special cases of stagewise independent and autoregressive processes commonly incorporated in stochastic programming. As with its two-stage counterpait, the MSD algorithm is shown to provide an asymptotically optimal solution, with probability one. As a by-product of this study, we also show that SD algorithms draw upon features of both approximate dynamic programming as well as stochastic programming. [ABSTRACT FROM AUTHOR]

Minimum-weight triangulation (MWT) is NP-hard. It has a polynomial-time constant-factor approximation algorithm, and a variety of effective polynomial-time heuristics that, for many instances, can find the exact MWT. Linear programs (LPs) for MWT are well-studied, but previously no connection was known between any LP and any approximation algorithm or heuristic for MWT. Here we show the first such connections: For an LP formulation due to Dantzig, Hoffman, and Hu [Math. Programming, 31 (1985), pp. 1-14], (i) the integrality gap is constant, and (ii) given any instance, if the aforementioned heuristics find the MWT, then so does the LP. [ABSTRACT FROM AUTHOR]

We give the first black-box reduction from approximation algorithms to truthful approximation mechanisms for a non-trivial class of multi-parameter problems. Specifically, we prove that every welfare-maximization problem that admits a fully polynomial-time approximation scheme (FPTAS) and can be encoded as a packing problem also admits a truthful-in-expectation randomized mechanism that is an FPTAS. Our reduction makes novel use of smoothed analysis by employing small perturbations as a tool in algorithmic mechanism design. We develop a "duality" between linear perturbations of the objective function of an optimization problem and of its feasible set, and we use the "primal" and "dual" viewpoints to prove the running time bound and the truthfulness guarantee, respectively, for our mechanism. [ABSTRACT FROM AUTHOR]

Given an undirected, capacitated graph G = (V, E) and a set K ⊂ V of terminals of size k, we construct an undirected, capacitated graph G' = (K, E') for which the cut function approximates the value of every minimum cut separating any subset U of terminals from the remaining terminals K - U. We refer to this graph G' as a cut-sparsifier, and we prove that there are cut-sparsifiers that can approximate all these minimum cuts in G to within an approximation factor that depends only polylogarithmically on k, the number of terminals. We prove such cut-sparsifiers exist through a zero-sum game, and we construct such sparsifiers through oblivious routing guarantees. These results allow us to derive a more general theory of Steiner cut and flow problems, and allow us to obtain approximation algorithms with guarantees independent of the size of the graph for a number of graph partitioning, graph layout, and multicommodity flow problems for which such guarantees were previously unknown. [ABSTRACT FROM AUTHOR]

We study the problem of computing correlation between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in three dimensions--polyhedral terrains--can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in O(n4/3 polylog n) expected time, where n is the total number of vertices in the graphs of the two functions. We also present approximation algorithms for minimizing the mean distance between the graphs of univariate and bivariate functions. For univariate functions we present a (1 + ε)-approximation algorithm that runs in O(n(1 +log²(1/ε))) expected time for any fixed ε > 0. The (1 + ε)-approximation algorithm for bivariate functions runs in O(n/ε) time, for any fixed ε > 0, provided the two functions are defined over the same triangulation of their domain. [ABSTRACT FROM AUTHOR]

The similarity of two polygonal curves can be measured using the Fréchet distance. We introduce the notion of a more robust Fréchet distance, where one is allowed to shortcut between vertices of one of the curves. This is a natural approach for handling noise, in particular batched outliers. We compute a (3 + ε)-approximation to the minimum Fréchet distance over all possible such shortcuts, in near linear time, if the curve is c-packed and the number of shortcuts is either small or unbounded. To facilitate the new algorithm we develop several new tools: (a) a data structure for preprocessing a curve (not necessarily c-packed) that supports (1 + ε)-approximate Fréchet distance queries between a subcurve (of the original curve) and a line segment; (b) a near linear time algorithm that computes a permutation of the vertices of a curve, such that any prefix of 2k - 1 vertices of this permutation forms an optimal approximation (up to a constant factor) to the original curve compared to any polygonal curve with k vertices, for any k > 0; and (c) a data structure for preprocessing a curve that supports approximate Fréchet distance queries between a subcurve and query polygonal curve. The query time depends quadratically on the complexity of the query curve and only (roughly) logarithmically on the complexity of the original curve. To our knowledge, these are the first data structures to support these kind of queries efficiently. [ABSTRACT FROM AUTHOR]

Reduced order models, in particular the reduced basis method, rely on empirically built and problem dependent basis functions that are constructed during an off-line stage. In the online stage, the precomputed problem-dependent solution space, that is spanned by the basis functions, can then be used in order to reduce the size of the computational problem. For complex problems, the number of basis functions required to guarantee a certain error tolerance can become too large in order to benefit computationally from the model reduction. To overcome this, the present work introduces a framework where local approximation spaces (in parameter space) are used to define the reduced order approximation in order to have explicit control over the on-line cost. This approach also adapts the local approximation spaces to local anisotropic behavior in the parameter space. We present the algorithm and numerous numerical tests. [ABSTRACT FROM AUTHOR]

We study integrality gaps and approximability of three closely related problems on directed graphs with edge lengths that satisfy the triangle inequality. Given two specified vertices s and t, two of these problems ask to find an s-t path in the graph visiting all other vertices. In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total length of this path. In the directed latency problem, the objective is to minimize the sum of the latencies of the vertices, where the latency of a vertex v is the distance from s to v along the path. The third problem that we study is the k-person ATSPP, in which the goal is to find k paths from s to t, of minimum total length, such that every vertex is on at least one of these paths. All of these problems are NP-hard. The best known approximation algorithms for ATSPP had ratio O(log n) [C. Chekuri and M. Pal, Theory Comput., 3 (2007), pp. 197--209], [U. Feige and M. Singh, "Improved approximation ratios for traveling salesperson tours and paths in directed graphs," in Proceedings of the 10th APPROX, 2007, pp. 107--118] until the recent result that improves it to O(log n/ log log n) [A. Asadpour et al., "An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem," in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 379--389], [U. Feige and M. Singh, "Improved approximation ratios for traveling salesperson tours and paths in directed graphs," in Proceedings of the 10th APPROX, 2007, pp. 107--118]. However, the best known bound on the integrality gap of any linear programming relaxation for ATSPP is only O(√n). For directed latency, the best previously known approximation algorithm has a guarantee of O(n½+∈) for any constant ε > 0 [V. Nagarajan and R. Ravi, "The directed minimum latency problem," in Proceedings of the 11th APPROX, 2008, pp. 193--206]. We present a new algorithm for the ATSPP problem that has an approximation ratio of O(log n), but whose analysis also upper bounds the integrality gap of the standard LP relaxation of ATSPP by the same factor. This solves an open problem posed in [C. Chekuri and M. Pal, Theory Comput., 3 (2007), pp. 197--209]. We then pursue a deeper study of this linear program and its variations, which leads to an O(log n)-approximation for the directed latency problem, a significant improvement over previously known results. Our result for k-person ATSPP is an O(k² log n)-approximation that bounds the integrality gap of a linear programming relaxation by the same factor. We are not aware of any previous work on this problem. [ABSTRACT FROM AUTHOR]

This work develops asynchronous stochastic approximation (SA) algorithms for networked systems with multiagents and regime-switching topologies to achieve consensus control. There are several distinct features of the algorithms: (1) In contrast to most of the existing consensus algorithms, the participating agents compute and communicate in an asynchronous fashion without using a global clock. (2) The agents compute and communicate at random times. (3) The regimeswitching process is modeled as a discrete-time Markov chain with a finite state space. (4) The functions involved are allowed to vary with respect to time; hence, nonstationarity can be handled. (5) Multiscale formulation enriches the applicability of the algorithms. In the setup, the switching process contains a rate parameter ε > 0 in the transition probability matrix that characterizes how frequently the topology switches. The algorithm uses a step-size μ that defines how fast the network states are updated. Depending on their relative values, three distinct scenarios emerge. Under suitable conditions, it is shown that a continuous-time interpolation of the iterates converges weakly either to a system of randomly switching ordinary differential equations modulated by a continuous-time Markov chain or to a system of differential equations (an average with respect to certain measure). In addition, a scaled sequence of tracking errors converges to either a switching diffusion or a diffusion. Simulation results are presented to demonstrate these findings. [ABSTRACT FROM AUTHOR]

We consider the general polynomial optimization problem P : /* = min{f(x) : x ∈ K}, where K is a compact basic semialgebraic set. We first show that the standard Lagrangian relaxation yields a lower bound as close as desired to the global optimum /*, provided that it is applied to a problem P equivalent to P, in which sufficiently many redundant constraints (products of the initial ones) are added to the initial description of P. Next we show that the standard hierarchy of linear program (LP-)relaxations of P (in the spirit of the Sherali--Adams reformulation-linearization technique) can be interpreted as a brute force simplification of the above Lagrangian relaxation in which a nonnegative polynomial (with coefficients to be determined) is replaced with a constant polynomial equal to zero. Inspired by this interpretation, we provide a systematic improvement of the LP-hierarchy by doing a much less brutal simplification which results into a parametrized hierarchy of semidefinite programs (and not LPs any more). For each semidefinite program in the parametrized hierarchy, the semidefinite constraint has a fixed size O(nk), independent of the rank in the hierarchy. When applied to a nontrivial class of convex problems, the first relaxation of the parametrized hierarchy is exact, in contrast with the LP-hierarchy, where convergence cannot be finite. [ABSTRACT FROM AUTHOR]