Packing and covering with integral feasible flows in integral supply-demand networks

Polynomial-time algorithms are presented for solving combinatorial packing and covering problems defined from the integral feasible flows in an integral supply-demand network. These algorithms are also shown to apply to packing and covering problems defined by the minimal integral solutions to general totally unimodular systems. Analogous problems arising from matroid bases are also discussed and it is demonstrated that a means for solving such problems is provided by recent work of Cunningham.     

The ellipsoid method and its consequences in combinatorial optimization

L. G. Khachiyan recently published a polynomial algorithm to check feasibility of a system of linear inequalities. The method is an adaptation of an algorithm proposed by Shor for non-linear optimization problems. In this paper we show that the method also yields interesting results in combinatorial optimization. Thus it yields polynomial algorithms for vertex packing in perfect graphs; for the matching and matroid intersection problems; for optimum covering of directed cuts of a digraph; for the minimum value of a submodular set function; and for other important combinatorial problems. On the negative side, it yields a proof that weighted fractional chromatic number is NP-hard. Research by the third author was supported by the Netherlands Organisation for the Advancement of Pure Research (Z.W.O.).     

Persistency in combinatorial optimization problems on matroids

Optimization problems on matroids are generalizations of such important combinatorial optimization problems like the problem of minimum spanning tree of a graph, the bipartite matching problem, flow problems, etc. We analyze algorithms for finding the maximum weight independent set of a matroid and for finding a maximum cardinality intersection of two matroids and extend them to obtain the so-called “persistency” partition of the basic set of the matroid, where contain elements belonging to all optimum solutions; contain elements not belonging to any optimum solution; contain elements that belong to some but not to all optimum solutions.     

The image of weighted combinatorial problems

The concept ofimage of an integrally weighted combinatorial problem is introduced as the vector of all possible weights of feasible solutions. This preliminary work begins to explore the possible applications of this concept and to study the computational complexity of image computations. It is shown that the images of spanning trees, matroid bases, perfect matchings and, more generally, matroid parity bases can be computed in polynomial time for some "bottleneck" objective functions (such as, for instance, the maximum weight of an element), whereas (random) pseudo-polynomial time is needed when the objective function is the sum of the element weights.     

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…     

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 weighted independent even factor algorithm

An even factor in a digraph is a vertex-disjoint collection of directed cycles of even length and directed paths. An even factor is called independent if it satisfies a certain matroid constraint. The problem of finding an independent even factor of maximum size is a common generalization of the nonbipartite matching and matroid intersection problems. In this paper, we present a primal-dual algorithm for the weighted independent even factor problem in odd-cycle-symmetric weighted digraphs. Cunningham and Geelen have shown that this problem is solvable via valuated matroid intersection. Their method yields a combinatorial algorithm running in O(n ³ γ +? n ⁶ m) time, where n and m are the number of vertices and edges, respectively, and γ is the time for an independence test. In contrast, combining the weighted even factor and independent even factor algorithms, our algorithm works more directly and runs in O(n ⁴ γ?+?n ⁵) time. The algorithm is fully combinatorial, and thus provides a new dual integrality theorem which commonly extends the total dual integrality theorems for matching and matroid intersection.     

K best solutions to combinatorial optimization problems

We review the Lawler-Murty [24,20] procedure for finding theK best solutions to combinatorial optimization problems. Then we introduce an alternative algorithm which is based on a binary search tree procedure. We apply both algorithms to the problems of finding theK best bases in a matroid, perfect matchings, and best cuts in a network.Partially supported by the National Science Foundation, No. ECS-8412926.     

A combinatorial generalization of polytopes

Primoids and duoids are collections of subsets of a fixed finite set with a natural generalization of a pivoting property of convex polytopes. This structure is precisely what is necessary for the application of complementary pivoting algorithms. This paper investigates the combinatorial structure of primoids and duoids, showing them to form the circuits and cocircuits of a binary matroid. This matroid is then compared with the simplicial geometries of Crapo and Rota.     

A Linear Programming Construction of Fully Optimal Bases in Graphs and Hyperplane Arrangements

The fully optimal basis of a bounded acyclic oriented matroid on a linearly ordered set has been defined and studied by the present authors in a series of papers, dealing with graphs, hyperplane arrangements, and oriented matroids (in order of increasing generality). This notion provides a bijection between bipolar orientations and uniactive internal spanning trees in a graph resp. bounded regions and uniactive internal bases in a hyperplane arrangement or an oriented matroid (in the sense of Tutte activities). This bijection is the basic case of a general activity preserving bijection between reorientations and subsets of an oriented matroid, called the active bijection, providing bijective versions of various classical enumerative results.Fully optimal bases can be considered as a strenghtening of optimal bases from linear programming, with a simple combinatorial definition. Our first construction used this purely combinatorial characterization, providing directly an algorithm to compute in fact the reverse bijection. A new definition uses a direct construction in terms of a linear programming. The fully optimal basis optimizes a sequence of nested faces with respect to a sequence of objective functions (whereas an optimal basis in the usual sense optimizes one vertex with respect to one objective function). This note presents this construction in terms of graphs and linear algebra.     

Algorithms and codes for the assignment problem

This paper analyzes the most efficient algorithms for the Linear Min-Sum Assignment Problem and shows that they derive from a common basic procedure. For each algorithm, we evaluate the computational complexity and the average performance on randomly-generated test problems. Efficient FORTRAN implementations for the case of complete and sparse matrices are given.Research supported by C.N.R., Progetto Finalizzato Informatica-SOFMAT, Italy.     

Full transversal matroids, strict gammoids, and the matroid components problem

We provide two algorithms for finding dependence graphs both in a full transversal matroid and in its dual, a strict gammoid. The first algorithm is based on directed paths in the directed graph associated with a strict gammoid; its complexity is O(|L|(|V-L|+|E|)), where L is the link-set of the gammoid. The second algorithm is based on a special property of Gaussian elimination in a matrix of indeterminates representing a full transversal matroid; it complexity is o(m²n), where m is the rank of the matroid and n the cardinality of the underlying set. We provide an algorithm for listing all bases in, and calculating the Whitney and Tutte polynomials for, a full transversal matroid or a strict gammoid. The complexity of this algorithm is 0(N(n-m) (|E| + m²)), where N is the number of bases.     

Heuristically guided algorithm for k-parity matroid problems

It is known that a large class of “hard” combinatorial optimization problems can be put in the form of a k-parity (weighted) matroid problem. In this paper we describe a heuristically guided algorithm for solving the above class of problems, which utilizes the information obtainable from the problem domain by computing, at each step, a possibly tight lower bound to the solution.     

On the (co)girth of a connected matroid

This article studies the girth and cogirth problems for a connected matroid. The problem of finding the cogirth of a graphic matroid has been intensively studied, but studies on the equivalent problem for a vector matroid or a general matroid have been rarely reported. Based on the duality and connectivity of a matroid, we prove properties associated with the girth and cogirth of a matroid whose contraction or restriction is disconnected. Then, we devise algorithms that find the cogirth of a matroid M from the matroids associated with the direct sum components of the restriction of M. As a result, the problem of finding the (co)girth of a matroid can be decomposed into a set of smaller sub-problems, which helps alleviate the computation. Finally, we implement and demonstrate the application of our algorithms to vector matroids.     

On computation complexity problems concerning relation algebras

In this paper, we study the computation complexity of some algebraic combinatorial problems that are closely associated with the graph isomorphism problem. The key point of our considerations is a relation algebra which is a combinatorial analog of a cellular algebra. We present upper bounds on the complexity of central algorithms for relation algebras such as finding the standard basis of extensions and intersection of relation algebras. Also, an approach is described to the graph isomorphism problem involving Schurian relation algebras (these algebras arise from the centralizing rings of permutation groups). We also discuss a number of open problems and possible directions for further investigation. Bibliography: 18 titles. Translated by I. N.Ponomarenko. Translated fromZapiski Nauchnykh Seminarov POMI, Vol 202, 1992, pp. 116–134.     

Ejection chain and filter-and-fan methods in combinatorial optimization

The design of effective neighborhood structures is fundamentally important for creating better local search and metaheuristic algorithms for combinatorial optimization. Significant efforts have been made to develop larger and more powerful neighborhoods that are able to explore the solution space more effectively while keeping computation complexity within acceptable levels. The most important advances in this domain derive from dynamic and adaptive neighborhood constructions originating in ejection chain methods and a special form of a candidate list design that constitutes the core of the filter-and-fan method. The objective of this paper is to lay out the general framework of the ejection chain and filter-and-fan methods and present applications to a number of important combinatorial optimization problems. The features of the methods that make them effective in these applications are highlighted to provide insights into solving challenging problems in other settings.     

Weighted matching with pair restrictions

The weighted matroid parity problems for the matching matroid and gammoids are among the very few cases for which the weighted matroid parity problem is polynomial time solvable. In this work we extend these problems to a general revenue function for each pair, and show that the resulting problem is still solvable in polynomial time via a standard weighted matching algorithm. We show that in many other directions, extending our results further is impossible (unless P = NP). One consequence of the new polynomial time algorithm is that it demonstrates, for the first time, that a prize-collecting assignment problem with “pair restriction” is solved in polynomial time. The prize collecting assignment problem is a relaxation of the prize-collecting traveling salesman problem which requires, for any prescribed pair of nodes, either both nodes of the pair are matched or none of them are. It is shown that the prize collecting assignment problem is equivalent to the prize collecting cycle cover problem which is hence solvable in polynomial time as well.     

Solving the weighted MAX-SAT problem using the dynamic convexized method

Satisfiability (SAT) and maximum satisfiability (MAX-SAT) are difficult combinatorial problems that have many important real-world applications. In this paper we investigate the performance of the dynamic convexized method based heuristics on the weighted MAX-SAT problem. We first present an auxiliary function which is constructed based on a penalty function, and minimize the function by a local search method which can escape successfully from previously converged local minimizers by increasing the value of a parameter. Two algorithms of the approach are implemented and compared with the Greedy Randomized Adaptive Search Procedure (GRASP) and the GRASP with Path Relinking (GRASP + PR). Experimental results illustrate efficient and faster convergence of our two algorithms.     

Checking oriented matroid isomorphism by means of canonical labeling

In this paper a method for establishing the structural equivalence of sets of planar geometric features composed by points and lines is presented. It is based on oriented matroid theory, a setting in which the combinatorial structural properties of these geometric features, such as incidence, order, partitioning, separation, and convexity, can be represented and analyzed in a coordinate-free manner. Projective transformations in computer vision keep in general the convexity property which implies an invariant oriented matroid representation of the planar geometric features under this class of transformations. As long as points and lines are in general position, the oriented matroid representation is also insensitive to small changes in the geometric image features. However the oriented matroid representation depends on the labeling of its elements. Checking the structural equivalence of the above mentioned geometric features represented by means of oriented matroids implies establishing whether two oriented matroid representations are equivalent up to relabeling of their elements. This is the oriented matroid isomorphism problem which is solved in this paper by means of a canonical labeling of the elements.