Submodular set functions,matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem

For the problem maxlcub;Z(S): S is an independent set in the matroid Xrcub;, it is well-known that the greedy algorithm finds an optimal solution when Z is an additive set function (Rado-Edmonds theorem). Fisher, Nemhauser and Wolsey have shown that, when Z is a nondecreasing submodular set function satisfying Z(?)=0, the greedy algorithm finds a solution with value at least half the optimum value. In this paper we show that it finds a solution with value at least 1/(1 + α) times the optimum value, where α is a parameter which represents the ‘total curvature’ of Z. This parameter satisfies 0≤α≤1 and α=0 if and only if the set function Z is additive. Thus the theorems of Rado-Edmonds and Fisher-Nemhauser-Wolsey are both contained in the bound 1/(1 + α). We show that this bound is best possible in terms of α. Another bound which generalizes the Rado-Edmonds theorem is given in terms of a ‘greedy curvature’ of the set function. Unlike the first bound, this bound can prove the optimality of the greedy algorithm even in instances where Z is not additive. A third bound, in terms of the rank and the girth of X, unifies and generalizes the bounds (e?1)/e known for uniform matroids and $\text{1}\text{2}$ for general matroids. We also analyze the performance of the greedy algorithm when X is an independence system instead of a matroid. Then we derive two bounds, both tight: The first one is [1?(1?α/K)^k]/α where K and k are the sizes of the largest and smallest maximal independent sets in X respectively; the second one is 1/(p+α) where p is the minimum number of matroids that must be intersected to obtain X.     

Computable Error Bounds for Semidefinite Programming

We study computability and applicability of error bounds for a given semidefinite pro-gramming problem under the assumption that the recession function associated with the constraint system satisfies the Slater condition. Specifically, we give computable error bounds for the distances between feasible sets, optimal objective values, and optimal solution sets in terms of an upper bound for the condition number of a constraint system, a Lipschitz constant of the objective function, and the size of perturbation. Moreover, we are able to obtain an exact penalty function for semidefinite programming along with a lower bound for penalty parameters. We also apply the results to a class of statistical problems.     

A Tight Analysis of the Greedy Algorithm for Set Cover

We establish significantly improved bounds on the performance of the greedy algorithm for approximatingset cover. In particular, we provide the first substantial improvement of the 20-year-old classical harmonic upper bound,H(m), of Johnson, Lovász, and Chvátal, by showing that the performance ratio of the greedy algorithm is, in fact,exactlyln m − ln ln m + Θ(1), wheremis the size of the ground set. The difference between the upper and lower bounds turns out to be less than 1.1. This provides the first tight analysis of the greedy algorithm, as well as the first upper bound that lies belowH(m) by a function going to infinity withm. We also show that the approximation guarantee for the greedy algorithm is better than the guarantee recently established by Srinivasan for the randomized rounding technique, thus improving the bounds on theintegrality gap. Our improvements result from a new approach which might be generally useful for attacking other similar problems.     

Quasiminimal crystals with a volume constraint and uniform rectifiability

We establish here, in a quite general context, uniform rectifiability properties for quasiminimal crystals with a volume constraint. Namely we prove that to any quasiminimal crystal with a volume constraint corresponds a unique equivalent open set whose boundary is Ahlfors-regular and which satisfies the so-called condition B. Moreover implicit bounds in these properties, which imply the uniform rectifiability of the boundary, can be chosen universal. As a consequence we give a universal upper bound for the number of connected components of reduced quasiminimizers and we also prove that quasiminimal crystals with a volume constraint actually satisfy, in some universal way, an apparently stronger quasiminimality condition where admissible perturbations are not required to be volume-preserving anymore.     

Worst case analysis of a class of set covering heuristics

In [2], Chvatal provided the tight worst case bound of the set covering greedy heuristic. We considered a general class of greedy type set covering heuristics. Their worst case bounds are dominated by that of the greedy heuristic.     

Greedy Families for Linear Objective Functions

The following structures are characterized: for which families of feasible subsets of a finite set does the greedy algorithm return the optimum subset independent of the weighting of a linear objective function on the set? Characteristically, the family must then have as bases the bases of a matroid (even when the feasible family is not a system of independent sets), and for every accessible feasible set X, the subset of elements by which X can be augmented is the complement of a proper closed set of the matroid. Another characterization is given for a family in which the greedy algorithm gives the optimum subset at every stage: the family is that of the bases of a sequence of matroid strong maps resulting in a natural duality theory. Theoretical underpinnings are given for several classical instances such as the algorithms of Kruskal, Prim, and Dijkstra.     

A MacWilliams type identity for matroids

In this paper, we consider the coboundary polynomial for a matroid as a generalization of the weight enumerator of a linear code. By describing properties of this polynomial and of a more general polynomial, we investigate the matroid analogue of the MacWilliams identity. From coding-theoretical approaches, upper bounds are given on the size of circuits and cocircuits of a matroid, which generalizes bounds on minimum Hamming weights of linear codes due to I. Duursma.     

Equivalent Conditions for Local Error Bounds

In this paper we present two classes of equivalent conditions for local error bounds in finite dimensional spaces. We formulate conditions of the first class by using subderivatives, subdifferentials and strong slopes for nearby points outside the referenced set, and show that these conditions actually characterize a uniform version of the local error bound property. We demonstrate this uniformity for the max function of a finite collection of smooth functions, and as a consequence we show that quasinormality constraint qualifications guarantee the existence of local error bounds. We further present the second class of equivalent conditions for local error bounds by using the various limits defined on the boundary of the referenced set. In presenting these conditions, we exploit the variational geometry of the referenced set in a systematic way and unify some existing results in the literature.     

Connected Covering Numbers

A connected covering is a design system in which the corresponding block graph is connected. The minimum size of such coverings are called connected coverings numbers. In this paper, we present various formulas and bounds for several parameter settings for these numbers. We also investigate results in connection with Turán systems. Finally, a new general upper bound, improving an earlier result, is given. The latter is used to improve upper bounds on a question concerning oriented matroid due to Las Vergnas.     

Random sampling and greedy sparsification for matroid optimization problems

Random sampling is a powerful tool for gathering information about a group by considering only a small part of it. We discuss some broadly applicable paradigms for using random sampling in combinatorial optimization, and demonstrate the effectiveness of these paradigms for two optimization problems on matroids: finding an optimum matroid basis and packing disjoint matroid bases. Application of these ideas to the graphic matroid led to fast algorithms for minimum spanning trees and minimum cuts. An optimum matroid basis is typically found by agreedy algorithm that grows an independent set into an optimum basis one element at a time. This continuous change in the independent set can make it hard to perform the independence tests needed by the greedy algorithm. We simplify matters by using sampling to reduce the problem of finding an optimum matroid basis to the problem of verifying that a givenfixed basis is optimum, showing that the two problems can be solved in roughly the same time. Another application of sampling is to packing matroid bases, also known as matroid partitioning. Sampling reduces the number of bases that must be packed. We combine sampling with a greedy packing strategy that reduces the size of the matroid. Together, these techniques give accelerated packing algorithms. We give particular attention to the problem of packing spanning trees in graphs, which has applications in network reliability analysis. Our results can be seen as generalizing certain results from random graph theory. The techniques have also been effective for other packing problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Some of this work done at Stanford University, supported by National Science Foundation and Hertz Foundation Graduate Fellowships, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation and Xerox Corporation. Also supported by NSF award 962-4239.     

Properly Weighted Independence Systemsand Applications to Scheduling Problems

1.IntroductionIncombinatorialoptimizationthetheoryofindependencesystemsplaysanimportantrole.Oneofthereasonswasthatawiderangeofpracticalproblemscanbeformulatedasthemaximumweightindependentsetproblem(MWIprobleminshort)onanindependencesystem.AmatroidisaspecialindependencesystemwiththecharacterizationthatthegreedyalgorithmcanalwaysworkforthecorrespondingMWIproblemwithanyweightfunction.Thisisafundamentalgreedilysolvablecase11,21.Theothergreedilysolvablecaseshavereceivedstronginterestsinrecentyea…     

A unified approach to error bounds for structured convex optimization problems

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.     

Lower Bounds on the Generalized Central Moments of the Optimal Alignments Score of Random Sequences

We present a general approach to the problem of determining tight asymptotic lower bounds for generalized central moments of the optimal alignment score of two independent sequences of i.i.d. random variables. At first, these are obtained under a main assumption for which sufficient conditions are provided. When the main assumption fails, we nevertheless develop a “uniform approximation” method leading to asymptotic lower bounds. Our general results are then applied to the length of the longest common subsequences of binary strings, in which case asymptotic lower bounds are obtained for the moments and the exponential moments of the optimal score. As a by-product, a local upper bound on the rate function associated with the length of the longest common subsequences of two binary strings is also obtained.     

An analysis of approximations for maximizing submodular set functions—I

LetN be a finite set andz be a real-valued function defined on the set of subsets ofN that satisfies z(S)+z(T)z(ST)+z(ST) for allS, T inN. Such a function is called submodular. We consider the problem max_SN{a(S):|S|K,z(S) submodular}.Several hard combinatorial optimization problems can be posed in this framework. For example, the problem of finding a maximum weight independent set in a matroid, when the elements of the matroid are colored and the elements of the independent set can have no more thanK colors, is in this class. The uncapacitated location problem is a special case of this matroid optimization problem.We analyze greedy and local improvement heuristics and a linear programming relaxation for this problem. Our results are worst case bounds on the quality of the approximations. For example, whenz(S) is nondecreasing andz(0) = 0, we show that a greedy heuristic always produces a solution whose value is at least 1 –[(K – 1)/K] ^K times the optimal value. This bound can be achieved for eachK and has a limiting value of (e – 1)/e, where e is the base of the natural logarithm.On leave of absence from Cornell University and supported, in part, by NSF Grant ENG 75-00568.Supported, in part, by NSF Grant ENG 76-20274.     

Performance guarantees of greedy algorithms for the problems on hereditary systems

Under study are the problems of maximization and minimization of additive functions on hereditary systems which generalize many computationally hard combinatorial optimization problems. A performance guarantee of the greedy algorithm is proven in terms of the parameters of a feasible set and the objective function of the maximization problem. This bound improves the well-known Jenkyns—Korte—Hausmann bound. An analogous result is obtained for the minimization problem of an additive function on a hereditary system.     

Feature extraction algorithms for constrained global optimization I. Mathematical foundation

Nonconvex mixed integer nonlinear programming problems arise quite frequently in engineering decision problems, in general, and in chemical process design synthesis and process scheduling applications, in particular. These problems are characterized by high dimensionality and multiple local optimal solutions. In this work, a novel approach is developed for determining the global optimum in nonlinear continuous and discrete domains. The mathematical foundations of the feature extraction algorithm are presented and the properties of the algorithm discussed in detail. The algorithm uses a partition and search strategy in which the problem domain is successively partitioned and a statistical approximation approach is used to characterize the objective function values and the constraint feasibility over a partition. Specifically, the general joint distribution function representing the objective function values is relaxed to a separable form and approximated using an expansion in terms of Bernstein functions. The coefficients of the expansion are determined by solving a small linear program. Feasibility is established by computing upper and lower bounds for the inequality constraint functions, while equality constraints are explicitly or numerically eliminated. Estimates of the volume averaged values of objective function and constraint feasibility are used to select efficient partitions for further investigation. These are refined successively so as to focus the search on the most promising decision regions. An alternative, constant resolution partitioning strategy is also developed using a suitably modified genetic search algorithm. Illustrative examples are used to demonstrate the key computational features of the method.     

Superpolynomial Lower Bounds for Monotone Span Programs

monotone span programs computing explicit functions. The best previous lower bound was by Beimel, Gál, Paterson [7]; our proof exploits a general combinatorial lower bound criterion from that paper. Our lower bounds are based on an analysis of Paley-type bipartite graphs via Weil's character sum estimates. We prove an lower bound for the size of monotone span programs for the clique problem. Our results give the first superpolynomial lower bounds for linear secret sharing schemes. We demonstrate the surprising power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae. We also show that the perfect matching function can be computed by polynomial size (non-monotone) span programs over arbitrary fields. Received: August 1, 1996     

On parallelizing a greedy heuristic for finding small dominant sets

We analyse a greedy heuristic for finding small dominating sets in graphs: bounds on the size of the dominating set so produced had previously been derived in terms of the size of a smallest dominating set and the number of vertices and edges in the graph, respectively, We show that computing the resulting small dominating set isP-hard and so cannot be done efficiently in parallel (in the context of the PRAM model of parallel computation). We also consider a related non-deterministic greedy heuristic.     

Convergence bounds for nonlinear programming algorithms

Bounds on convergence are given for a general class of nonlinear programming algorithms. Methods in this class generate at each interation both constraint multipliers and approximate solutions such that, under certain specified assumptions, accumulation points of the multiplier and solution sequences satisfy the Fritz John or the Kuhn—Tucker optimality conditions. Under stronger assumptions, convergence bounds are derived for the sequences of approximate solution, multiplier and objective function values. The theory is applied to an interior—exterior penalty function algorithm modified to allow for inexact subproblem solutions. An entirely new convergence bound in terms of the square root of the penalty controlling parameter is given for this algorithm.     

A rough set approach to the characterization of transversal matroids

Rough sets are efficient for data pre-processing during data mining. However, some important problems such as attribute reduction in rough sets are NP-hard and the algorithms required to solve them are mostly greedy ones. The transversal matroid is an important part of matroid theory, which provides well-established platforms for greedy algorithms. In this study, we investigate transversal matroids using the rough set approach. First, we construct a covering induced by a family of subsets and we propose the approximation operators and upper approximation number based on this covering. We present a sufficient condition under which a subset is a partial transversal, and also a necessary condition. Furthermore, we characterize the transversal matroid with the covering-based approximation operator and construct some types of circuits. Second, we explore the relationships between closure operators in transversal matroids and upper approximation operators based on the covering induced by a family of subsets. Finally, we study two types of axiomatic characterizations of the covering approximation operators based on the set theory and matroid theory, respectively. These results provide more methods for investigating the combination of transversal matroids with rough sets.