Two algorithms for weighted matroid intersection

Consider a finite setE, a weight functionw:E→R, and two matroidsM ₁ andM ₂ defined onE. The weighted matroid intersection problem consists of finding a setI⊆E, independent in both matroids, that maximizes Σ{w(e):e inI}. We present an algorithm of complexity O(nr(r+c+logn)) for this problem, wheren=|E|,r=min(rank(M ₁), rank (M ₂)),c=max (c ₁,c ₂) and, fori=1,2,c _i is the complexity of finding the circuit ofI∪{e} inM _i (or show that none exists) wheree is inE andI⊆E is independent inM ₁ andM ₂. A related problem is to find a maximum weight set, independent in both matroids, and of given cardinalityk (if one exists). Our algorithm also solves this problem. In addition, we present a second algorithm that, given a feasible solution of cardinalityk, finds an optimal one of the same cardinality. A sensitivity analysis on the weights is easy to perform using this approach. Our two algorithms are related to existing algorithms. In fact, our framework provides new simple proofs of their validity. Other contributions of this paper are the existence of nonnegative reduced weights (Theorem 6), allowing the improved complexity bound, and the introduction of artificial elements, allowing an improved start and flexibility in the implementation of the algorithms. This research was supported in part by NSF grant ECS 8503192 to Carnegie-Mellon University.     

Solving the linear matroid parity problem as a sequence of matroid intersection problems

In this paper, we present an O(r ⁴ n) algorithm for the linear matroid parity problem. Our solution technique is to introduce a modest generalization, the non-simple parity problem, and identify an important subclass of non-simple parity problems called easy parity problems which can be solved as matroid intersection problems. We then show how to solve any linear matroid parity problem parametrically as a sequence of easy parity problems.In contrast to other algorithmic work on this problem, we focus on general structural properties of dual solutions rather than on local primal structures. In a companion paper, we develop these ideas into a duality theory for the parity problem.     

Approximation algorithms for k-partitioning problems with partition matroid constraint

The $k$ -partitioning problem with partition matroid constraint is to partition the union of $k$ given sets of size $m$ into $m$ sets such that each set contains exactly one element from each given set. With the objective of minimizing the maximum load, we present an efficient polynomial time approximation scheme (EPTAS) for the case where $k$ is a constant and a full polynomial time approximation scheme (FPTAS) for the case where $m$ is a constant; with the objective of maximizing the minimum load, we present a $\frac{1}{k-1}$ -approximation algorithm for the general case, an EPTAS for the case where $k$ is a constant; with the objective of minimizing the $l_p$ -norm of the load vector, we prove that the layered LPT algorithm (Wu and Yao in Theor Comput Sci 374:41–48, 2007) is an all-norm 2-approximation algorithm.     

Concentration inequalities for nonlinear matroid intersection

In this work we propose new randomized rounding algorithms for matroid intersection and matroid base polytopes. We prove concentration inequalities for polynomial objective functions and constraints that has numerous applications and can be used in approximation algorithms for Minimum Quadratic Spanning Tree, Unrelated Parallel Machines Scheduling and scheduling with time windows and nonlinear objectives. We also show applications related to Constraint Satisfaction and dense polynomial optimization. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 541–571, 2015     

Persistency and matroid intersection

In this paper, we show that for any independence system, the problem of finding a persistency partition of the ground set and that of finding a maximum weight independent set are polynomially equivalent. This research has been partially funded by the Greek Ministry of Education under the program Pythagoras.     

Packing of arborescences with matroid constraints via matroid intersection

Mathematical Programming - Edmonds’ arborescence packing theorem characterizes directed graphs that have arc-disjoint spanning arborescences in terms of connectivity. Later he also observed a...     

New algorithms for lineark-matroid intersection and matroidk-parity problems

We present algorithms for thek-Matroid Intersection Problem and for the Matroidk-Parity Problem when the matroids are represented over the field of rational numbers andk > 2. The computational complexity of the algorithms is linear in the cardinality and singly exponential in the rank of the matroids. As an application, we describe new polynomially solvable cases of thek-Dimensional Assignment Problem and of thek-Dimensional Matching Problem. The algorithms use some new identities in multilinear algebra including the generalized Binet—Cauchy formula and its analogue for the Pfaffian. These techniques extend known methods developed earlier fork = 2.A preliminary version of this paper appeared in the Proceedings of the Second IPCO Conference [2].Supported by the Mittag-Leffler Institute and KTH, Stockholm.     

An unbounded matroid intersection polyhedron

A characterization of the maximum-cardinality common independent sets of two matroids via an unbounded convex polyhedron is proved, confirming a conjecture of D.R. Fulkerson. A similar result, involving a bounded polyhedron, is the well-known matroid intersection polyhedron theorem of Jack Edmonds; Edmonds's theorem is used in the proof.     

The intersection of a matroid and a simplicial complex

A classical theorem of Edmonds provides a min-max formula relating the maximal size of a set in the intersection of two matroids to a ``covering" parameter. We generalize this theorem, replacing one of the matroids by a general simplicial complex. One application is a solution of the case of a matroidal version of Ryser's conjecture. Another is an upper bound on the minimal number of sets belonging to the intersection of two matroids, needed to cover their common ground set. This, in turn, is used to derive a weakened version of a conjecture of Rota. Bounds are also found on the dual parameter--the maximal number of disjoint sets, all spanning in each of two given matroids. We study in detail the case in which the complex is the complex of independent sets of a graph, and prove generalizations of known results on ``independent systems of representatives" (which are the special case in which the matroid is a partition matroid). In particular, we define a notion of -matroidal colorability of a graph, and prove a fractional version of a conjecture, that every graph is -matroidally colorable.

The methods used are mostly topological.

     

A family of reductions for Schubert intersection problems

We produce a family of reductions for Schubert intersection problems whose applicability is checked by calculating a linear combination of the dimensions involved. These reductions do not alter the Littlewood–Richardson coefficient, and this fact is connected to known multiplicative properties of these coefficients.     

Efficient algorithms for orthogonal packing problems

The NP complete problem of the orthogonal packing of objects of arbitrary dimension is considered in the general form. A new model for representing objects in containers is proposed that ensures the fast design of an orthogonal packing. New heuristics for the placement of orthogonal packing are proposed. A single-pass heuristic algorithm and a multimethod genetic algorithm are developed that optimize an orthogonal packing solution by increasing the packing density. Numerical experiments for two- and three-dimensional orthogonal packing problems are performed.     

A matroid view of key theorems for edge-swapping algorithms

We demonstrate that two key theorems of Amaldi et?al. (Math Methods Oper Res 69:205?C223, 2009), which they presented with rather complicated proofs, can be more easily and cleanly established using a simple and classical property of binary matroids. Besides a simpler proof, we see that both of these key results are manifestations of the same essential property.     

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.     

Matroid intersection algorithms

LetM ₁ = (E, 9₁),M ₂ = (E, 9₂) be two matroids over the same set of elementsE, and with families of independent sets 9₁, 9₂. A setI 9₁ 9₂ is said to be anintersection of the matroidsM ₁,M ₂. An important problem of combinatorial optimization is that of finding an optimal intersection ofM ₁,M ₂. In this paper three matroid intersection algorithms are presented. One algorithm computes an intersection containing a maximum number of elements. The other two algorithms compute intersections which are of maximum total weight, for a given weighting of the elements inE. One of these algorithms is primal-dual, being based on duality considerations of linear programming, and the other is primal. All three algorithms are based on the computation of an augmenting sequence of elements, a generalization of the notion of an augmenting path from network flow theory and matching theory. The running time of each algorithm is polynomial inm, the number of elements inE, and in the running times of subroutines for independence testing inM ₁,M ₂. The algorithms provide constructive proofs of various important theorems of matroid theory, such as the Matroid Intersection Duality Theorem and Edmonds' Matroid Polyhedral Intersection Theorem.Research sponsored by the Air Force Office of Scientific Research Grant 71-2076.     

A new algorithm for the intersection of a line with the independent set polytope of a matroid

We present a new algorithm for the problem of determining the intersection of a half-line with the independent set polytope of a matroid. We show it can also be used to compute the strength of a graph and the corresponding partition using successive contractions. The algorithm is based on the maximization of successive linear forms on the boundary of the polytope. We prove it is a polynomial algorithm in probability with average number of iterations in O(n⁵). Finally, numerical tests reveal that it should only require O(n²) iterations in practice.     

Some open problems on excluding a uniform matroid

It would appear that minor-closed classes of matroids that are representable over any given finite field are very well behaved. This paper explores what happens when we go a little further to minor-closed classes of matroids that exclude a uniform minor. Numerous open problems of varying difficulty are posed.