A characterization of bounded convex approximation properties

The characterization of bounded approximation properties defined by arbitrary operator ideals due to Oja is extended to bounded convex approximation properties. As an application, it is shown that the unique extension property of a Banach space X enables to lift the metric convex approximation property from a Banach space X to its dual space X*.     

Finding curves on general spaces through quantitative topology,with applications to Sobolev and Poincaré inequalities

In many metric spaces one can connect an arbitrary pair of points with a curve of finite length, but in Euclidean spaces one can connect a pair of points with a lot of rectifiable curves, curves that are well distributed across a region. In the present paper we give geometric criteria on a metric space under which we can find similar families of curves. We shall find these curves by first solving a dual problem of building Lipschitz maps from our metric space into a sphere with good topological properties. These families of curves can be used to control the values of a function in terms of its gradient (suitably interpreted on a general metric space), and to derive Sobolev and Poincaré inequalities.The author is supported by the U.S. National Science Foundation and grateful to IHES for its hospitality.     

Convergence of the Approximate Auxiliary Problem Method for Solving Generalized Variational Inequalities

We consider an extension of the auxiliary problem principle for solving a general variational inequality problem. This problem consists in finding a zero of the sum of two operators defined on a real Hilbert space H: the first is a monotone single-valued operator; the second is the subdifferential of a lower semicontinuous proper convex function . To make the subproblems easier to solve, we consider two kinds of lower approximations for the function : a smooth approximation and a piecewise linear convex approximation. We explain how to construct these approximations and we prove the weak convergence and the strong convergence of the sequence generated by the corresponding algorithms under a pseudo Dunn condition on the single-valued operator. Finally, we report some numerical experiences to illustrate the behavior of the two algorithms.     

On Convex Limit Sets and Brownian Motion

We prove limsup results for nonnegative functionals of convex sets determined by normalized Brownian paths in Banach spaces. This continues the interesting investigation of D. Khoshnevisan into this area, and relates to some classical unsolved isoperimetric problems for the convex hull of curves in ^d. Section 4 contains the solution of a problem similar to these classical problems.     

Convexity preserving interpolation by algebraic curves and surfaces

The problem of interpolation by a convex curve to the vertices of a convex polygon is considered. A natural 1-parameter family ofC algebraic curves solving this problem is presented. This is extended to a solution, of a general Hermite-type problem, in, which the curve also interpolates to one or two prescribedtangents at any desired vertices of the polygon. The construction of these curves is a generalization of well known methods for generatingconic sections. Several properties of this family of algebraic curves are discussed. In addition, the method is generalized to convexC interpolation of strictly convex data sets inR ³ by algebraicsurfaces.     

Strongly convex weakly complex Berwald metrics and real Landsberg metrics

Under the assumption that' is a strongly convex weakly Khler Finsler metric on a complex manifold M, we prove that F is a weakly complex Berwald metric if and only if F is a real Landsberg metric.This result together with Zhong(2011) implies that among the strongly convex weakly Kahler Finsler metrics there does not exist unicorn metric in the sense of Bao(2007). We also give an explicit example of strongly convex Kahler Finsler metric which is simultaneously a complex Berwald metric, a complex Landsberg metric,a real Berwald metric, and a real Landsberg metric.     

On polyhedral approximations in an <Emphasis Type="Italic">n</Emphasis>-dimensional space

The polyhedral approximation of a positively homogeneous (and, in general, nonconvex) function on a unit sphere is investigated. Such a function is presupporting (i.e., its convex hull is the supporting function) for a convex compact subset of Rⁿ. The considered polyhedral approximation of this function provides a polyhedral approximation of this convex compact set. The best possible estimate for the error of the considered approximation is obtained in terms of the modulus of uniform continuous subdifferentiability in the class of a priori grids of given step in the Hausdorff metric.     

Convex approximations for complete integer recourse models

We consider convex approximations of the expected value function of a two-stage integer recourse problem. The convex approximations are obtained by perturbing the distribution of the random right-hand side vector. It is shown that the approximation is optimal for the class of problems with totally unimodular recourse matrices. For problems not in this class, the result is a convex lower bound that is strictly better than the one obtained from the LP relaxation.This research has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences.Key words.integer recourse – convex approximationMathematics Subject Classification (1991):90C15, 90C11     

Better <Emphasis Type="Italic">s</Emphasis>–<Emphasis Type="Italic">t</Emphasis>-tours by Gao trees

We consider the s–t-path TSP: given a finite metric space with two elements s and t, we look for a path from s to t that contains all the elements and has minimum total distance. We improve the approximation ratio for this problem from 1.599 to 1.566. Like previous algorithms, we solve the natural LP relaxation and represent an optimum solution \(x^*\) as a convex combination of spanning trees. Gao showed that there exists a spanning tree in the support of \(x^*\) that has only one edge in each narrow cut [i.e., each cut C with \(x^*(C)<2\)]. Our main theorem says that the spanning trees in the convex combination can be chosen such that many of them are such “Gao trees” simultaneously at all sufficiently narrow cuts.     

The deviation of polygonal functions in the Lp metric

The precise value is given of the upper bound of the deviation in the L_p metric (1 < p < ) of a function f(x) in the class H , given by a convex modulus of continuity(t), from its polygonal approximation at the points x_k=k/n (k=0, 1 ...,n).Translated from Matematicheskie Zametki, Vol. 5, No. 1, pp. 31–37, 1969.I would like to express my appreciation to A. A. Nudel'man for suggesting the problem considered here and for his help.     

Homogeneous manifolds from noncommutative measure spaces

Let M be a finite von Neumann algebra with a faithful normal trace τ. In this paper we study metric geometry of homogeneous spaces O of the unitary group UM of M, endowed with a Finsler quotient metric induced by the p-norms of τ, ‖xp_‖=τ(p|x|)^1/p, p?1. The main results include the following. The unitary group carries on a rectifiable distance dp induced by measuring the length of curves with the p-norm. If we identify O as a quotient of groups, then there is a natural quotient distance that metrizes the quotient topology. On the other hand, the Finsler quotient metric defined in O provides a way to measure curves, and therefore, there is an associated rectifiable distance dO,p. We prove that the distances and dO,p coincide. Based on this fact, we show that the metric space is a complete path metric space. The other problem treated in this article is the existence of metric geodesics, or curves of minimal length, in O. We give two abstract partial results in this direction. The first concerns the initial values problem and the second the fixed endpoints problem. We show how these results apply to several examples. In the process, we improve some results about the metric geometry of UM with the p-norm.     

On solving a D.C. programming problem by a sequence of linear programs

We are dealing with a numerical method for solving the problem of minimizing a difference of two convex functions (a d.c. function) over a closed convex set in ⁿ . This algorithm combines a new prismatic branch and bound technique with polyhedral outer approximation in such a way that only linear programming problems have to be solved.Parts of this research were accomplished while the third author was visiting the University of Trier, Germany, as a fellow of the Alexander von Humboldt foundation.     

The best one-sided approximation of one class of functions by another

We concern ourselves with problems of the best one-sided approximation of classes of continuous functions. We obtain estimates of the best one-sided approximation of one class of functions by another, and we find exact values of the upper bounds of the best one-sided approximations on the classes H of 2-periodic functions [given by an arbitrary convex modulus of continuity(t)] by trigonometric polynomials of order not higher thann–1 in the L₂ metric.Translated from Matematicheskie Zametki, Vol. 14, No. 5, pp. 627–632, November, 1973.     

Approximation algorithms for general packing problems and their application to the multicast congestion problem

In this paper we present approximation algorithms based on a Lagrangian decomposition via a logarithmic potential reduction to solve a general packing or min–max resource sharing problem with M non-negative convex constraints on a convex set B. We generalize a method by Grigoriadis et al. to the case with weak approximate block solvers (i.e., with only constant, logarithmic or even worse approximation ratios). Given an accuracy , we show that our algorithm needs calls to the block solver, a bound independent of the data and the approximation ratio of the block solver. For small approximation ratios the algorithm needs calls to the block solver. As an application we study the problem of minimizing the maximum edge congestion in a multicast communication network. Interestingly the block problem here is the classical Steiner tree problem that can be solved only approximately. We show how to use approximation algorithms for the Steiner tree problem to solve the multicast congestion problem approximately. This work was done in part when the second author was studying at the University of Kiel. This paper combines our extended abstracts of the 2nd IFIP International Conference on Theoretical Computer Science, TCS 2002, Montréal, Canada and the 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks, ARACNE 2002, Roma, Italy. This research was supported in part by the DFG - Graduiertenkolleg, Effiziente Algorithmen und Mehrskalenmethoden; by the EU Thematic Network APPOL I + II, Approximation and Online Algorithms, IST-1999-14084 and IST-2001-32007; by the EU Research Training Network ARACNE, Approximation and Randomized Algorithms in Communication Networks, HPRN-CT-1999-00112; by the EU Project CRESCCO, Critical Resource Sharing for Cooperation in Complex Systems, IST-2001-33135. The second author was also supported by an MITACS grant of Canada; and by the NSERC Discovery Grant DG 5-48923.     

An approximation algorithm for the general max-min resource sharing problem

We propose an approximation algorithm for, the general max-min resource sharing problem with M nonnegative concave constraints on a convex set B. The algorithm is based on a Lagrangian decomposition method and it uses a c-approximation algorithm (called approximate block solver) for a simpler maximization problem over the convex set B. We show that our algorithm achieves within iterations or calls to the approximate block solver a solution for the general max-min resource sharing problem with approximation ratio The algorithm is faster and simpler than the previous known approximation algorithms for the problem [12, 13] Research of the author was supported in part by EU Thematic Network APPOL, Approximation and Online Algorithms, IST-2001-30012, by EU Project CRESCCO, Critical Resource Sharing for Cooperation in Complex Systems, IST-2001-33135 and by DFG Project, Entwicklung und Analyse von Approximativen Algorithmen für Gemischte und Verallgemeinerte Packungs- und überdeckungsprobleme, JA 612/10-1. Part of this work was done while visiting the Department of Computer Science at ETH Zürich. An extended abstract of this paper appeared in SWAT 2004, Scandinavian Workshop on Algorithm Theory, LNCS 3111, 311–322.     

Shortest curves on convex hypersurfaces

We give a survey of results of the author on the geometry of geodesics and shortest curves on general convex hypersurfaces in spaces with constant curvature. We present qualitatively new theorems, which unite and generalize the main classical results; we give applications to the solution of a number of actual problems of geometry of convex surfaces in the large. We give generalizations of some well-known theorems on geodesics and shortest curves to Riemannian manifolds and nonregular multidimensional convex metrics.Translated from Itogi Nauki i Tekhniki, Seriya Problemy Geometrii, Vol. 16, pp. 155–194, 1984.     

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.     

A new ideal metric with applications to multivariate stable limit theorems

Summary A new ideal metric of orderr>1 is introduced on ^k and a thorough analysis of its metric properties is given. In comparison to the known ideal metric of Zolotarev this new metric allows estimates from above by pseudo difference moments and thus allows applications to stable limit theorems. As applications we give the right order Berry-Esséen type result in the stable case, obtain the limiting behaviour of multivariate summability methods and discuss the approximation problem by compound Poisson distributions.Research supported by NATO GRANT CRG 900 798 and by a DFG Grant     

On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls

We consider the outer approximation problem of finding a minimum radius ball enclosing a given intersection of at most n − 1 balls in . We show that if the aforementioned intersection has a nonempty interior, then the problem reduces to minimizing a convex quadratic function over the unit simplex. This result is established by using convexity and representation theorems for a class of quadratic mappings. As a byproduct of our analysis, we show that a class of nonconvex quadratic problems admits a tight semidefinite relaxation.     

ℓ1-Minimization with Magnitude Constraints in the Frequency Domain

In this paper, we study the -optimal control problem with additional constraints on the magnitude of the closed-loop frequency response. In particular, we study the case of magnitude constraints at fixed frequency points (a finite number of such constraints can be used to approximate an -norm constraint). In previous work, we have shown that the primal-dual formulation for this problem has no duality gap and both primal and dual problems are equivalent to convex, possibly infinite-dimensional, optimization problems with LMI constraints. Here, we study the effect of approximating the convex magnitude constraints with a finite number of linear constraints and provide a bound on the accuracy of the approximation. The resulting problems are linear programs. In the one-block case, both primal and dual programs are semi-infinite dimensional. The optimal cost can be approximated, arbitrarily well from above and within any predefined accuracy from below, by the solutions of finite-dimensional linear programs. In the multiblock case, the approximate LP problem (as well as the exact LMI problem) is infinite-dimensional in both the variables and the constraints. We show that the standard finite-dimensional approximation method, based on approximating the dual linear programming problem by sequences of finite-support problems, may fail to converge to the optimal cost of the infinite-dimensional problem.