Submodular linear programs on forests

A general linear programming model for an order-theoretic analysis of both Edmonds' greedy algorithm for matroids and the NW-corner rule for transportation problems with Monge costs is introduced. This approach includes the model of Queyranne, Spieksma and Tardella (1993) as a special case. We solve the problem by optimal greedy algorithms for rooted forests as underlying structures. Other solvable cases are also discussed.     

Greedy algorithm and symmetric matroids

Symmetric matroids are set systems which are obtained, in some sense, by a weakening of the structure of a matroid. These set systems are characterized by a greedy algorithm and they are suitable for dealing with autodual properties of matroids. Applications are given to the eulerian tours of 4-regular graphs and the theory ofg-matroids.     

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.     

基于覆盖上近似算子的拟阵结构及其关系

Covering-based rough sets,as a technique of granular computing,can be a useful tool for dealing with inexact,uncertain or vague knowledge in information systems.Matroids generalize linear independence in vector spaces,graph theory and provide well established platforms for greedy algorithm design.In this paper,we construct three types of matroidal structures of covering-based rough sets.Moreover,through these three types of matroids,we study the relationships among these matroids induced by six types of covering-based upper approximation operators.First,we construct three families of sets by indiscernible neighborhoods,neighborhoods and close friends,respectively.Moreover,we prove that they satisfy independent set axioms of matroids.In this way,three types of matroidal structures of covering-based rough sets are constructed.Secondly,we study some characteristics of the three types of matroid,such as dependent sets,circuits,rank function and closure.Finally,by comparing independent sets,we study relationships among these matroids induced by six types of covering-based upper approximation operators.     

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.     

On the vertices of the -additive core

The core of a game v on N, which is the set of additive games φ dominating v such that φ(N)=v(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Möbius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds’ theorem for the greedy algorithm), which characterize the vertices of the core.     

The Greedy Algorithm and Coxeter Matroids

The notion of matroid has been generalized to Coxeter matroid by Gelfand and Serganova. To each pair (W, P) consisting of a finite irreducible Coxeter group W and parabolic subgroup P is associated a collection of objects called Coxeter matroids. The (ordinary) matroids are a special case, the case W = A (isomorphic to the symmetric group Sym_{_n+1}) and P a maximal parabolic subgroup. The main result of this paper is that for Coxeter matroids, just as for ordinary matroids, the greedy algorithm provides a solution to a naturally associated combinatorial optimization problem. Indeed, in many important cases, Coxeter matroids are characterized by this property. This result generalizes the classical Rado-Edmonds and Gale theorems.A corollary of our theorem is that, for Coxeter matroids L, the greedy algorithm solves the L-assignment problem. Let W be a finite group acting as linear transformations on a Euclidean space , and let

Strongly inequivalent representations and Tutte polynomials of matroids

We develop constructive techniques to show that non-isomorphic 3-connected matroids that are representable over a fixed finite field and that have the same Tutte polynomial abound. In particular, for most prime powers q, we construct infinite families of sets of 3-connected matroids for which the matroids in a given set are non-isomorphic, are representable over GF(q), and have the same Tutte polynomial. Furthermore, the cardinalities of the sets of matroids in a given family grow exponentially as a function of rank, and there are many such families.In Memory of Gian-Carlo Rota     

On the geometric structure of independence systems

A bouquet of matroids is a combinatorial structure that generalizes the properties of matroids. Given an independence system, there exist several bouquets of matroids having the same family of independent sets. We show that the collection of these geometries forms in general a meet semi-lattice and, in some cases, a lattice (for instance, when is the family of the stable sets in a graph). Moreover, one of the bouquets that correspond to the highest elements in the meet semi-lattice provides the smallest decomposition of into matroidal families, such that the rank functions of the different matroids have the same values for common sets. In the last section, we give sharp bounds on the performance of the greedy algorithm, using parameters of some special bouquets in the semi-lattice.     

Oriented matroids, complex manifolds, and a combinatorial model for BU

We introduce a new notion of complex oriented matroid and develop some basic properties of this object. Our definition of complex oriented matroids bears the same relationship to classical oriented matroids that the stratification of the complex plane into nine components corresponding to the signs of the complex and real parts has with the three-component sign stratification of the real line. We then use these complex oriented matroids to set up the foundations of a combinatorial version of complex geometry analogous to MacPherson's combinatorial differential manifolds; in this world, the representing object for the functor of (combinatorial) complex vector bundles is the nerve of a poset of complex oriented matroids. We conclude by showing that this space is homotopy equivalent to the complex Grassmannian, thus deducing that our combinatorial world is able to completely capture the notion of complex vector bundles.     

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.     

Four matroidal structures of covering and their relationships with rough sets

Covering is a common form of data representation, and covering-based rough sets serve as an efficient technique to process this type of data. However, many important problems such as covering reduction in covering-based rough sets are NP-hard so that most algorithms to solve them are greedy. Matroids provide well-established platforms for greedy algorithm foundation and implementation. Therefore, it is necessary to integrate covering-based rough set with matroid. In this paper, we propose four matroidal structures of coverings and establish their relationships with rough sets. First, four different viewpoints are presented to construct these four matroidal structures of coverings, including 1-rank matroids, bigraphs, upper approximation numbers and transversals. The respective advantages of these four matroidal structures to rough sets are explored. Second, the connections among these four matroidal structures are studied. It is interesting to find that they coincide with each other. Third, a converse view is provided to induce a covering by a matroid. We study the relationship between this induction and the one from a covering to a matroid. Finally, some important concepts of covering-based rough sets, such as approximation operators, are equivalently formulated by these matroidal structures. These interesting results demonstrate the potential to combine covering-based rough sets with matroids.     

Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems

Min-max problems on matroids are NP-hard for a wide variety of matroids. However, greedy type algorithms have data independent worst case performance guarantees, andn-enumerative algorithms yield-optimal solutions ifn is sufficiently close to the rank of the underlying matroid. Data dependent performance guarantees can be obtained for max-min problems over matroids.This research was partially supported by NSERC Grant A5543.     

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.     

A Greedy Algorithm for Capacitated Lot-Sizing Problems

We show that the convex hull of the set of feasible solutions of single-item capacitated lot-sizing problem (CLSP) is a base polyhedron of a polymatroid. We present a greedy algorithm to solve CLSP with linear objective function. The proposed algorithm is an effective implementation of the classical Edmonds' algorithm for maximizing linear function over a polymatroid. We consider some special cases of CLSP with nonlinear objective function that can be solved by the proposed greedy algorithm in O ( n ) time.     

The -digraph optimization problem and the greedy algorithm

In this paper we present a new optimization problem and a general class of objective functions for this problem. We show that optimal solutions to this problem with these objective functions are found with a simple greedy algorithm. Special cases include matroids, Huffman's data compression problem, a special class of greedoids, a special class of min cost max flow problems (related to Monge sequences), a special class of weighted f-factor problems, and some new problems.     

Matroid representation of clique complexes

In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) which is also called a flag complex, and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of “how complex a graph is with respect to the maximum weighted clique problem” since a greedy algorithm is a k-approximation algorithm for this problem. For any k>0, we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be n-1. Other related investigations are also given.     

A theoretical justification of the set covering greedy heuristic of Caprara et al.

Large scale set covering problems have often been approached by constructive greedy heuristics, and much research has been devoted to the design and evaluation of various greedy criteria for such heuristics. A criterion proposed by Caprara et al. (1999) is based on reduced costs with respect to the yet unfulfilled constraints, and the resulting greedy heuristic is reported to be superior to those based on original costs or ordinary reduced costs.We give a theoretical justification of the greedy criterion proposed by Caprara et al. by deriving it from a global optimality condition for general non-convex optimisation problems. It is shown that this criterion is in fact greedy with respect to incremental contributions to a quantity which at termination coincides with the deviation between a Lagrangian dual bound and the objective value of the feasible solution found.     

有向拟阵与贪婪算法

有向拟阵是拟阵的一种有向情形.本文证明了有向拟阵可用贪婪算法进行刻划.     

A characterization of orthogonal duality in matroid theory

An operation on matroids is a function defined from the collection of all matroids on finite sets to itself which preserves isomorphism of matroids and sends a matroid on a set S to a matroid on the same set S. We show that orthogonal duality is the only non-trivial operation on matroids which interchanges contraction and deletion.