Matroid bases with cardinality constraints on the intersection

Mathematical Programming - Given two matroids $$\mathcal {M}_{1} = (E, \mathcal {B}_{1})$$ and $$\mathcal {M}_{2} = (E, \mathcal {B}_{2})$$ on a common ground set E with base sets $$\mathcal...     

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.     

Approximate implicitization and recursive surface intersection algorithms

Most published work on intersection algorithms for Computer Aided Design (CAD) systems addresses transversal intersections [1], situations where the surface normals of the surfaces intersected are well separated along all intersection curves. For transversal intersections the divide and conquer strategy of recursive subdivision, Sinha's theorem [2] and the convex hull property of NonUniform Rational B-Spline surfaces (NURBS) efficiently identify all intersection branches. However, in singular or near singular intersections, situations where the surfaces are parallel or near parallel in an intersection region, along an intersection curve or in an intersection point, even deep levels of subdivision will frequently not sort out the intersection topology. The paper will focus on the novel approach of Approximate Implicitization to address these challenges. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

双圈拟阵

Sim■es Pereira于1992年提出双圈拟阵.本文讨论了(i)双圈拟阵及其秩函数;(ii)次模函数在双圈拟阵中的应用;(iii)双圈拟阵B(G)的横贯拟阵.主要结果:1°由圈矩阵Bf=[I,Bf12]和圈秩的概念,推出M(f0)为双圈拟阵;2°证明了双圈拟阵B(G)等于由子集族{Av∶v∈V(G)},e与v在G中相关联}所确定的横贯拟阵;3°用不同于Matthews(1977)的方法证明了(iii).     

Efficient algorithms for a family of matroid intersection problems

Consider a matroid where each element has a real-valued cost and a color, red or green; a base is sought that contains q red elements and has smallest possible cost. An algorithm for the problem on general matroids is presented, along with a number of variations. Its efficiency is demonstrated by implementations on specific matroids. In all cases but one, the running time matches the best-known algorithm for the problem without the red element constraint: On graphic matroids, a smallest spanning tree with q red edges can be found in time O(n log n) more than what is needed to find a minimum spanning tree. A special case is finding a smallest spanning tree with a degree constraint; here the time is only O(m + n) more than that needed to find one minimum spanning tree. On transversal and matching matroids, the time is the same as the best-known algorithms for a minimum cost base. This also holds for transversal matroids for convex graphs, which model a scheduling problem on unit-length jobs with release times and deadlines. On partition matroids, a linear-time algorithm is presented. Finally an algorithm related to our general approach finds a smallest spanning tree on a directed graph, where the given root has a degree constraint. Again the time matches the best-known algorithm for the problem without the red element (i.e., degree) constraint.     

障碍拟阵图

Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.     

Subdominant Matroid Ultrametrics

Given a matroid M on the ground set E, the Bergman fan or space of M-ultrametrics, is a polyhedral complex in which arises in several different areas, such as tropical algebraic geometry, dynamical systems, and phylogenetics. Motivated by the phylogenetic situation, we study the following problem: Given a point in we wish to find an M-ultrametric which is closest to it in the -metric. The solution to this problem follows easily from the existence of the subdominant M-ultrametric: a componentwise maximum M-ultrametric which is componentwise smaller than . A procedure for computing it is given, which brings together the points of view of matroid theory and tropical geometry. When the matroid in question is the graphical matroid of the complete graph K_n, the Bergman fan parameterizes the equidistant phylogenetic trees with n leaves. In this case, our results provide a conceptual explanation for Chepoi and Fichets method for computing the tree that most closely matches measured data.Received August 12, 2004     

拟阵的可去圈

本首先用拟阵语言将图论的新概念定义成了拟阵的新概念，然后用拟阵语言将Goddyn和Heuevl所得的图论上的新结果平移成了拟阵的新结果，最后用拟阵的方法对它们给出了新的证明。     

Inverse Matroid Intersection Problem

LetM ₁ andM ₂ be matroids onS,B be theirk-element common independent set, andw a weight function onS. Given two functionsb 0 andc 0 onS, the Inverse Matroid Intersection Problem (IMIP) is to determine a modified weight functionw such that (a)B becomes a maximum weight common independent set of cardinalityk underw, (b)c¦w — w¦ is minimum, and (c)¦w — w b. Many Inverse Combinatorial Optimization Problems can be considered as the special cases of the IMIP.In this paper we show that the IMIP can be solved in strongly polynomial time, and give a necessary and sufficient condition for the feasibility of the IMIP. Finally we extend the discussion to the version of the IMIP with Multiple Common Independent Sets.Research partially supported by the National Natural Science Foundation of China     

Matroid Enumeration for Incidence Geometry

Matroids are combinatorial abstractions for point configurations and hyperplane arrangements, which are fundamental objects in discrete geometry. Matroids merely encode incidence information of geometric configurations such as collinearity or coplanarity, but they are still enough to describe many problems in discrete geometry, which are called incidence problems. We investigate two kinds of incidence problem, the points–lines–planes conjecture and the so-called Sylvester–Gallai type problems derived from the Sylvester–Gallai theorem, by developing a new algorithm for the enumeration of non-isomorphic matroids. We confirm the conjectures of Welsh–Seymour on ≤11 points in ℝ³ and that of Motzkin on ≤12 lines in ℝ², extending previous results. With respect to matroids, this algorithm succeeds to enumerate a complete list of the isomorph-free rank 4 matroids on 10 elements. When geometric configurations corresponding to specific matroids are of interest in some incidence problems, they should be analyzed on oriented matroids. Using an encoding of oriented matroid axioms as a boolean satisfiability (SAT) problem, we also enumerate oriented matroids from the matroids of rank 3 on n≤12 elements and rank 4 on n≤9 elements. We further list several new minimal non-orientable matroids.     

Matroid basis graphs. I

A matroid may be defined as a collection of sets, called bases, which satisfy a certain exchange axiom. The basis graph of a matroid has a vertex for each basis and an edge for each pair of bases that differ by the exchange of a single pair of elements. Two characterizations of basis graphs are obtained. The first involves certain local subgraphs and how they lie when the given graph is leveled with respect to distance from a particular vertex. The second involves the existence of a special mapping from the given graph to some “full” basis graph. It is also shown that in a natural sense all basis graphs are homotopically trivial.     

Matroid matching and some applications

The polymatroid matching problem, also known as the matchoid problem or the matroid parity problem, is polynomially unsolvable in general but solvable for linear matroids. The solution for linear matroids is analysed and results concerning arbitrary matroids are given from which the linear case follows immediately. The same general result is then applied to find a maximum circuitfree partial hypergraph of a 3-uniform hypergraph, to generalize a theorem of Mader on packing openly disjoint paths starting and ending in a given set, and to study a problem in structural rigidity.