Exact and approximate resolution of integral multiflow and multicut problems: algorithms and complexity

This is a summary of the author’s PhD thesis supervised by Marie- Christine Costa and Frédéric Roupin and defended on 20 November 2006 at the Conservatoire National des Arts et Métiers in Paris (France). The thesis is written in French and is available upon request from the author. This work deals with two well-known optimization problems from graph theory: the maximum integral multiflow and the minimum multicut problems. The main contributions of this thesis concern the polynomial-time solvability and the approximation of these two problems (and of some of their variants) in classical classes of graphs: bounded tree-width graphs, planar graphs and grids, digraphs, etc.      

A note on the approximation of mildly nonlinear Dirichlet problems by finite differences

Summary In [9], Simpson proved some theorems concerning the approximation of mildly nonlinear Dirichlet problems –u=f (x, u) inD, u=0 on D by finite differences. The assumptionsf(x, 0)0 andf _u(x, u)>0 in [9] have turned out to be unnecessarily restrictive and are eliminated in this paper. On the other hand, we considered it necessary to make the smoothness conditions forD slightly more stringent irrespective of the conditions imposed onf.The results of this paper are already contained in the author's doctoral thesis [6]. Meanwhile, H.B. Keller (Math. Comp. 29, p. 464–476) has published a general theory on approximation methods for nonlinear problems which can be used for obtaining Theorem 1This work was performed under the terms of the agreement on association between the Max-Planck-Institut für Plasmaphysik and EURATOM     

Approximation and resolution of min–max and min–max regret versions of combinatorial optimization problems

This is a summary of the most important results presented in the author’s PhD thesis. This thesis, written in French, was defended on November 2005 and supervised by Cristina Bazgan and Daniel Vanderpooten. A copy is available from the author upon request. This thesis deals with the complexity, approximation and resolution of the min–max and min–max versions of classical combinatorial optimization problems. In addition to these theoretical aspects, a practical application of robustness approaches to the problem of data association is considered.     

Outer approximation algorithms for DC programs and beyond

This paper is a summary of the author’s Ph.D. thesis in Mathematics supervised by Giancarlo Bigi and Antonio Frangioni, and defended on 23 June 2008 at the Università di Pisa. The thesis is written in English and available from http://www.di.unipi.it/di/groups/optimize. The work deals with outer approximation algorithms for solving an alternative equivalent formulation and a novel generalization of canonical DC (difference of convex) programs. The thesis develops an in-depth investigation of structural properties of both problems, and of the impact of approximations onto the quality of approximate optimal solutions. It also propose hierarchies of conditions guaranteeing convergence and develops several different implementable algorithms for canonical DC programs and its novel generalization, respectively.     

SimultaneousL 1 approximation of a compact set of real-valued functions

Summary In this paper the uniqueness results found in simultaneous Chebychev approximation are extended to simultaneousL ₁ approximation. In particular a sufficient condition to guarantee uniqueness of a best approximate to aL ₁ compact set is given.This paper is taken in part from a thesis to be submitted by M. P. Carroll in partial fulfillment of the requirements for the Ph. D. degree in the Department of Mathematics at Rensselaer Polytechnic Institute.     

Global optimization of rational functions: a semidefinite programming approach

We consider the problem of global minimization of rational functions on (unconstrained case), and on an open, connected, semi-algebraic subset of , or the (partial) closure of such a set (constrained case). We show that in the univariate case (n = 1), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced in the PhD thesis of Jibetean [16]. This extends the analogous results by Nesterov [13] for global minimization of univariate polynomials. For the bivariate case (n = 2), we obtain a fully polynomial time approximation scheme (FPTAS) for the unconstrained problem, if an a priori lower bound on the infimum is known, by using results by De Klerk and Pasechnik [1]. For the NP-hard multivariate case, we discuss semidefinite programming-based relaxations for obtaining lower bounds on the infimum, by using results by Parrilo [15], and Lasserre [12].     

Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems

Due to their fundamental nature and numerous applications, sphere constrained polynomial optimization problems have received a lot of attention lately. In this paper, we consider three such problems: (i) maximizing a homogeneous polynomial over the sphere; (ii) maximizing a multilinear form over a Cartesian product of spheres; and (iii) maximizing a multiquadratic form over a Cartesian product of spheres. Since these problems are generally intractable, our focus is on designing polynomial-time approximation algorithms for them. By reducing the above problems to that of determining the L ₂-diameters of certain convex bodies, we show that they can all be approximated to within a factor of Ω((log n/n) ^d/2–1) deterministically, where n is the number of variables and d is the degree of the polynomial. This improves upon the currently best known approximation bound of Ω((1/n) ^d/2–1) in the literature. We believe that our approach will find further applications in the design of approximation algorithms for polynomial optimization problems with provable guarantees.     

Hereditary optimal control problems: Numerical method based upon a padé approximation

In this paper, we consider a particular approximation scheme which can be used to solve hereditary optimal control problems. These problems are characterized by variables with a time-delayed argumentx(t – ). In our approximation scheme, we first replace the variable with an augmented statey(t) x(t - ). The two-sided Laplace transform ofy(t) is a product of the Laplace transform ofx(t) and an exponential factor. This factor is approximated by a first-order Padé approximation, and a differential relation fory(t) can be found. The transformed problem, without any time-delayed argument, can then be solved using a gradient algorithm in the usual way. Four problems are solved to illustrate the validity and usefulness of this technique.This research was supported in part by the National Aeronautics and Space Administration under NASA Grant NCC-2-106.     

Near-circularity of the error curve in complex Chebyshev approximation

Let f(z) be analytic on the unit disk, and let p^*(z) be the best (Chebyshev) polynomial approximation to f(z) on the disk of degree at most n. It is observed that in typical problems the “error curve,” the image of the unit circle under (f − p^*)(z), often approximates to a startling degree a perfect circle with winding number n + 1. This phenomenon is approached by consideration of related problems whose error curves are exactly circular, making use of a classical theorem of Carathéodory and Fejér. This leads to a technique for calculating approximations in one step that are roughly as close to best as the best approximation error curve is close to circular, and hence to strong theorems on near-circularity as the radius of the domain shrinks to 0 or as n increases to ∞. As a computational example, very tight bounds are given for approximation of e^z on the unit disk. The generality of the near-circularity phenomenon (more general domains, rational approximation) is discussed.     

Level–wise Approximation of a Markov Process Associated to the Boundary of an Infinite Tree

We study an approximation of a Markov process associated to the boundary of an infinite rooted tree. This approximation is constructed by projecting the infinitesimal generator of the original process (defined on the boundary) onto the spaces associated to the filtration spanned by the successive levels of the rooted tree. S. Martínez and J. San Martín acknowledge the support by Nucleus Millenium Information and Randomness P04-069-F. D. Remenik current address: Center for Applied Mathematics, Cornell University, 657 Rhodes Hall, Ithaca, NY 14853. The author acknowledges the partial support by Nucleus Millenium Information and Randomness P01-005 for his work in his undergraduate thesis at Universidad de Chile.     

Best Approximation and Cyclic Variation Diminishing Kernels

We study best uniform approximation of periodic functions from

Full-size image

where the kernelK(x, y) is strictly cyclic variation diminishing, and related problems including periodic generalized perfect splines. For various approximation problems of this type, we show the uniqueness of the best approximation and characterize the best approximation by extremal properties of the error function. The results are proved by using a characterization of best approximants from quasi-Chebyshev spaces and certain perturbation results.     

On the advantage over a random assignment

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. This is a useful measure for optimization problems where the random assignment algorithm is known to give essentially the best possible polynomial time approximation. In this paper, we focus on this measure for the optimization problems Max‐Lin‐2 in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max‐k‐Lin‐2, a special case of the above problem in which each equation has at most k variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

On well posedness of best simultaneous approximation problems in Banach spaces

The well posedness of best simultaneous approximation problems is considered. We establish the generic results on the well posedness of the best simultaneous approximation problems for any closed weakly compact nonempty subset in a strictly convex Kadec Banach space. Further, we prove that the set of all points inE(G) such that the best simultaneous approximation problems are not well posed is a u- porous set inE(G) whenX is a uniformly convex Banach space. In addition, we also investigate the generic property of the ambiguous loci of the best simultaneous approximation.     

Quasi-regression

Quasi-regression is introduced for approximation of functions on the unit cube in s dimensions. It is computationally efficient, compared to kriging, for problems requiring a large number of function evaluations. This paper describes how to implement quasi-regression and shows how to estimate the approximation error using the same data used to build the approximation. Four example functions are investigated numerically.     

An integral function and vector sequence method for unconstrained global optimization

This paper studies the relationship between the so-called bi-quadratic optimization problem and its semidefinite programming (SDP) relaxation. It is shown that each r-bound approximation solution of the relaxed bi-linear SDP can be used to generate in randomized polynomial time an O(r){\mathcal{O}(r)}-approximation solution of the original bi-quadratic optimization problem, where the constant in O(r){\mathcal{O}(r)} does not involve the dimension of variables and the data of problems. For special cases of maximization model, we provide an approximation algorithm for the considered problems.     

How to Allocate Network Centers

This paper deals with the issue of allocating and utilizing centers in a distributed network, in its various forms. The paper discusses the significant parameters of center allocation, defines the resulting optimization problems, and proposes several approximation algorithms for selecting centers and for distributing the users among them. We concentrate mainly on balanced versions of the problem, i.e., in which it is required that the assignment of clients to centers be as balanced as possible. The main results are constant ratio approximation algorithms for the balanced κ-centers and balanced κ-weighted centers problems, and logarithmic ratio approximation algorithms for the ρ-dominating set and the k-tolerant set problems.     

Strong convergence of the iterative scheme based on the extragradient method for mixed equilibrium problems and fixed point problems of an infinite family of nonexpansive mappings

In this paper, we introduce an iterative scheme based on the extragradient approximation method for finding a common element of the set of common fixed points of a countable family of nonexpansive mappings, the set of solutions of a mixed equilibrium problem, and the set of solutions of the variational inequality problem for a monotone L-Lipschitz continuous mapping in a real Hilbert space. Then, the strong convergence theorem is proved under some parameters controlling conditions. Applications to optimization problems are given. The results obtained in this paper improve and extend the recent ones announced by Wangkeeree [R. Wangkeeree, An extragradient approximation method for equilibrium problems and fixed point problems of a countable family of nonexpansive mappings, Fixed Point Theory and Applications (2008) 17. doi:10.1155/2008/134148. Article ID 134148], Kumam and Katchang [P. Kumam, P. Katchang, A viscosity of extragradient approximation method for finding equilibrium problems, variational inequalities and fixed point problems for nonexpansive mappings, Nonlinear Anal. Hybrid Syst. (2009) doi:10.1016/j.nahs.2009.03.006] and many others.     

Besov regularity for second order elliptic boundary value problems with variable coefficients

This paper is concerned with some theoretical foundations for adaptive numerical methods for elliptic boundary value problems. The approximation order that can be achieved by such an adaptive method is determined by certain Besov regularity of the weak solution. We study Besov regularity for second order elliptic problems in bounded domains in ℝ ^d . The investigations are based on intermediate Schauder estimates and on some potential theoretic framework. Moreover, we use characterizations of Besov spaces by wavelet expansions. This work has been supported by the Deutsche Forschungsgemeinschaft (Da 360/1-1)     

A recurrence method for a special class of continuous time linear programming problems

This article studies a numerical solution method for a special class of continuous time linear programming problems denoted by (SP). We will present an efficient method for finding numerical solutions of (SP). The presented method is a discrete approximation algorithm, however, the main work of computing a numerical solution in our method is only to solve finite linear programming problems by using recurrence relations. By our constructive manner, we provide a computational procedure which would yield an error bound introduced by the numerical approximation. We also demonstrate that the searched approximate solutions weakly converge to an optimal solution. Some numerical examples are given to illustrate the provided procedure.     

Approximate <Emphasis Type="Italic">k</Emphasis>-MSTs and <Emphasis Type="Italic">k</Emphasis>-Steiner trees via the primal-dual method and Lagrangean relaxation

Garg [10] gives two approximation algorithms for the minimum-cost tree spanning k vertices in an undirected graph. Recently Jain and Vazirani [15] discovered primal-dual approximation algorithms for the metric uncapacitated facility location and k-median problems. In this paper we show how Gargs algorithms can be explained simply with ideas introduced by Jain and Vazirani, in particular via a Lagrangean relaxation technique together with the primal-dual method for approximation algorithms. We also derive a constant factor approximation algorithm for the k-Steiner tree problem using these ideas, and point out the common features of these problems that allow them to be solved with similar techniques.