The first eigenvalue of the Laplacian, isoperimetric constants, and the Max Flow Min Cut Theorem

We show how ‘test’ vector fields may be used to give lower bounds for the Cheeger constant of a Euclidean domain (or Riemannian manifold with boundary), and hence for the lowest eigenvalue of the Dirichlet Laplacian on the domain. Also, we show that a continuous version of the classical Max Flow Min Cut Theorem for networks implies that Cheeger’s constant may be obtained precisely from such vector fields. Finally, we apply these ideas to reprove a known lower bound for Cheeger’s constant in terms of the inradius of a plane domain. Received: 13 June 2005     

Packing T-joins

A consequence of Seymour's characterization of binary clutters with the Max Flow Min Cut property is that the minimum cardinality of a T-cut is equal to the largest number of edge-disjoint T-joins in every graph that cannot be T-contracted to an odd K_2,3. We give a simple “graphic” proof of this fact. © 1996 John Wiley & Sons, Inc.     

Approximation with a fixed number of solutions of some multiobjective maximization problems

We investigate the problem of approximating the Pareto set of some multiobjective optimization problems with a given number of solutions. Our purpose is to exploit general properties that many well studied problems satisfy. We derive existence and constructive approximation results for the biobjective versions of Max Submodular Symmetric Function (and special cases), Max Bisection, and Max Matching and also for the k-objective versions of Max Coverage, Heaviest Subgraph, Max Coloring of interval graphs.     

A primal–dual operation on sets linked with closed convex relaxation processes

We give some properties and uses of a primal–dual operation on sets that appear in the closed convex relaxation process (Hiriart-Urruty et al. in Rev. Mat. Iberoam. 27(2):449–474, 2011; López and Volle in J. Conv. Anal. 17(3–4):1057–1075, 2010). Applications are provided concerning a class of relaxed minimization problems in the frame of the so called B-regularization theory. Special attention is paid to the case when the initial problem admits optimal solutions under compactness assumptions.     

An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance

We consider the design of semidefinite programming(SDP) based approximation algorithm for the problem Max Hypergraph Cut with Limited Unbalance(MHC-LU): Find a partition of the vertices of a weighted hypergraph H =(V, E) into two subsets V1, V2 with ‖V2|- |V1‖ u for some given u and maximizing the total weight of the edges meeting both V1 and V2. The problem MHC-LU generalizes several other combinatorial optimization problems including Max Cut, Max Cut with Limited Unbalance(MC-LU), Max Set Splitting,Max Ek-Set Splitting and Max Hypergraph Bisection. By generalizing several earlier ideas, we present an SDP randomized approximation algorithm for MHC-LU with guaranteed worst-case performance ratios for various unbalance parameters τ = u/|V|. We also give the worst-case performance ratio of the SDP-algorithm for approximating MHC-LU regardless of the value of τ. Our strengthened SDP relaxation and rounding method improve a result of Ageev and Sviridenko(2000) on Max Hypergraph Bisection(MHC-LU with u = 0), and results of Andersson and Engebretsen(1999), Gaur and Krishnamurti(2001) and Zhang et al.(2004) on Max Set Splitting(MHC-LU with u = |V|). Furthermore, our new formula for the performance ratio by a tighter analysis compared with that in Galbiati and Maffioli(2007) is responsible for the improvement of a result of Galbiati and Maffioli(2007) on MC-LU for some range of τ.     

Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs

We generalize all the results obtained for integer multiflow and multicut problems in trees by Garg et al. [N. Garg, V.V. Vazirani and M. Yannakakis, Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18 (1997) 3–20] to planar graphs with a fixed number of faces, although other classical generalizations do not lead to such results. We also introduce the class of k-edge-outerplanar graphs and bound the integrality gap for the maximum edge-disjoint paths problem in these graphs.     

Approximate duality for vector quasi-equilibrium problems and applications

In this paper, we introduce new versions of ?-dual problems of a vector quasi-equilibrium problem with set-valued maps, and we give an ?-duality result between approximate solutions of the primal and dual problems. As the first application of the main result, we obtain an ?-duality for a vector quasi-equilibrium problem whose ?-solutions are understood in the sense of proper efficiency. The second application is devoted to an?-duality for a vector optimization problem with set-valued maps.     

Duality theorems for a new class of multitime multiobjective variational problems

In this work, we consider a new class of multitime multiobjective variational problems of minimizing a vector of functionals of curvilinear integral type. Based on the normal efficiency conditions for multitime multiobjective variational problems, we study duals of Mond-Weir type, generalized Mond-Weir-Zalmai type and under some assumptions of (??, b)-quasiinvexity, duality theorems are stated. We give weak duality theorems, proving that the value of the objective function of the primal cannot exceed the value of the dual. Moreover, we study the connection between values of the objective functions of the primal and dual programs, in direct and converse duality theorems. While the results in §1 and §2 are introductory in nature, to the best of our knowledge, the results in §3 are new and they have not been reported in literature.     

Sparse effective membership problems via residue currents

We use residue currents on toric varieties to obtain bounds on the degrees of solutions to polynomial ideal membership problems. Our bounds depend on (the volume of) the Newton polytope of the polynomial system and are therefore well adjusted to sparse polynomial systems. We present sparse versions of Max N?ther??s AF?+?BG Theorem, Macaulay??s Theorem, and Kollár??s Effective Nullstellensatz, as well as recent results by Hickel and Andersson?CG?tmark.     

Some local approximation properties of simple point processes

For simple point processes ξ on a Borel space S, we prove some approximations involving conditional distributions, given that ξ hits a small set B. Beginning with general versions of some classical limit theorems, going back to the pioneering work of Palm and Khinchin, we proceed to prove that, under suitable regularity conditions, the contributions to B and B ^c are asymptotically conditionally independent. We further derive approximations in total variation of reduced Palm distributions and show that, when ξ hits some small sets B ₁,..., B _n , the corresponding restrictions are asymptotically independent. Next we give general versions of the asymptotic relations P{ξ B > 0} ~ Eξ B and prove some ratio limit theorems for conditional expectations E[η | ξ B > 0], valid even when Eξ is not σ-finite and the Palm distributions may fail to exist.     

Jacobi Polynomials,Weighted Sobolev Spaces and Approximation Results of Some Singularities

In this paper, we give some polynomial approximation results in a class of weighted Sobolev spaces, which are related to the Jacobi operator. We further give some embeddings of those weighted Sobolev spaces into usual ones and into spaces of continuous functions, in order to use the above approximation results in the p‐version (or the spectral method) of some finite or boundary element methods. Finally, two typical examples of the polynomial approximation of some singularities of boundary value problems in polygonal or polyhedral domains are presented.     

Complexity issues on bounded restrictive H-coloring

We consider a bounded version of the restrictive and the restrictive list H-coloring problem in which the number of pre-images of certain vertices of H is taken as parameter. We consider the decision and the counting versions, as well as, further variations of those problems. We provide complexity results identifying the cases when the problems are NP-complete or #P-complete or polynomial time solvable. We conclude stating some open problems.     

On the polynomial Lindenstrauss theorem

Under certain hypotheses on the Banach space X, we show that the set of N-homogeneous polynomials from X to any dual space, whose Aron–Berner extensions are norm attaining, is dense in the space of all continuous N-homogeneous polynomials. To this end we prove an integral formula for the duality between tensor products and polynomials. We also exhibit examples of Lorentz sequence spaces for which there is no polynomial Bishop–Phelps theorem, but our results apply. Finally we address quantitative versions, in the sense of Bollobás, of these results.     

On the existence of positive solutions and their continuous dependence on functional parameters for some class of elliptic problems

We discuss the existence and the dependence on functional parameters of solutions of the Dirichlet problem for a kind of the generalization of the balance of a membrane equation. Since we shall propose an approach based on variational methods, we treat our equation as the Euler-Lagrange equation for a certain integral functional J. We will not impose either convexity or coercivity of the functional. We develop a duality theory which relates the infimum on a special set X of the energy functional associated with the problem, to the infimum of the dual functional on a corresponding set X^d. The links between minimizers of both functionals give a variational principle and, in consequence, their relation to our boundary value problem. We also present the numerical version of the variational principle. It enables the numerical characterization of approximate solutions and gives a measure of a duality gap between primal and dual functional for approximate solutions of our problem.     

Sampling subproblems of heterogeneous Max‐Cut problems and approximation algorithms

Recent work in the analysis of randomized approximation algorithms for NP‐hard optimization problems has involved approximating the solution to a problem by the solution of a related subproblem of constant size, where the subproblem is constructed by sampling elements of the original problem uniformly at random. In light of interest in problems with a heterogeneous structure, for which uniform sampling might be expected to yield suboptimal results, we investigate the use of nonuniform sampling probabilities. We develop and analyze an algorithm which uses a novel sampling method to obtain improved bounds for approximating the Max‐Cut of a graph. In particular, we show that by judicious choice of sampling probabilities one can obtain error bounds that are superior to the ones obtained by uniform sampling, both for unweighted and weighted versions of Max‐Cut. Of at least as much interest as the results we derive are the techniques we use. The first technique is a method to compute a compressed approximate decomposition of a matrix as the product of three smaller matrices, each of which has several appealing properties. The second technique is a method to approximate the feasibility or infeasibility of a large linear program by checking the feasibility or infeasibility of a nonuniformly randomly chosen subprogram of the original linear program. We expect that these and related techniques will prove fruitful for the future development of randomized approximation algorithms for problems whose input instances contain heterogeneities. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

An Inexact Modified Subgradient Algorithm for Primal-Dual Problems via Augmented Lagrangians

We consider a primal optimization problem in a reflexive Banach space and a duality scheme via generalized augmented Lagrangians. For solving the dual problem (in a Hilbert space), we introduce and analyze a new parameterized Inexact Modified Subgradient (IMSg) algorithm. The IMSg generates a primal-dual sequence, and we focus on two simple new choices of the stepsize. We prove that every weak accumulation point of the primal sequence is a primal solution and the dual sequence converges weakly to a dual solution, as long as the dual optimal set is nonempty. Moreover, we establish primal convergence even when the dual optimal set is empty. Our second choice of the stepsize gives rise to a variant of IMSg which has finite termination.     

L p -Norms, Log-Barriers and Cramer Transform in Optimization

We show that the Laplace approximation of a supremum by L ^p -norms has interesting consequences in optimization. For instance, the logarithmic barrier functions (LBF) of a primal convex problem P and its dual P ^* appear naturally when using this simple approximation technique for the value function g of P or its Legendre–Fenchel conjugate g ^*. In addition, minimizing the LBF of the dual P ^* is just evaluating the Cramer transform of the Laplace approximation of g. Finally, this technique permits to sometimes define an explicit dual problem P ^* in cases when the Legendre–Fenchel conjugate g ^* cannot be derived explicitly from its definition.     

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     

A bound for the number of different basic solutions generated by the simplex method

In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the simplex method for linear programming problems (LP) having optimal solutions. The bound is polynomial of the number of constraints, the number of variables, and the ratio between the minimum and the maximum values of all the positive elements of primal basic feasible solutions. When the problem is primal nondegenerate, it becomes a bound for the number of iterations. The result includes strong polynomiality for Markov Decision Problem by Ye (http://www.stanford.edu/~yyye/simplexmdp1.pdf, 2010) and utilize its analysis. We also apply our result to an LP whose constraint matrix is totally unimodular and a constant vector b of constraints is integral.     

On generalizations of network design problems with degree bounds

Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely laminar crossing spanning tree), and (2) by incorporating ‘degree bounds’ in other combinatorial optimization problems such as matroid intersection and lattice polyhedra. We give new or improved approximation algorithms, hardness results, and integrality gaps for these problems. Our main result is a (1, b + O(log n))-approximation algorithm for the minimum crossing spanning tree (MCST) problem with laminar degree constraints. The laminar MCST problem is a natural generalization of the well-studied bounded-degree MST, and is a special case of general crossing spanning tree. We give an additive Ω(log ^c m) hardness of approximation for general MCST, even in the absence of costs (c > 0 is a fixed constant, and m is the number of degree constraints). This also leads to a multiplicative Ω(log ^c m) hardness of approximation for the robust k-median problem (Anthony et al. in Math Oper Res 35:79–101, 2010), improving over the previously known factor 2 hardness. We then consider the crossing contra-polymatroid intersection problem and obtain a (2, 2b + Δ ? 1)-approximation algorithm, where Δ is the maximum element frequency. This models for example the degree-bounded spanning-set intersection in two matroids. Finally, we introduce the crossing latticep olyhedron problem, and obtain a (1, b + 2Δ ? 1) approximation algorithm under certain condition. This result provides a unified framework and common generalization of various problems studied previously, such as degree bounded matroids.