A note on some algorithms for matroids

We use results on the optimal basis of a matroid to modify two algorithms, one which finds the circuits of a matroid from the bases, and one which finds the bases from the cocircuits.     

Binary signed-graphic matroids: Representations and recognition algorithms

Recognition algorithms determining whether a given matroid is binary signed-graphic or not are presented in this work. Depending on whether the input is a cographic, a binary or a general matroid different algorithms are provided utilizing mainly decomposition results for the class of signed-graphic matroids. Finally, in order to devise such algorithms, necessary results regarding the representability of signed-graphic matroids in various fields are also given.     

Two algorithms for global optimization

In this paper, we develop and compare two methods for solving the problem of determining the global maximum of a function over a feasible set. The two methods begin with a random sample of points over the feasible set. Both methods then seek to combine these points into “regions of attraction” which represent subsets of the points which will yield the same local maximums when an optimization procedure is applied to points in the subset. The first method for constructing regions of attraction is based on approximating the function by a mixture of normal distributions over the feasible region and the second involves attempts to apply cluster analysis to form regions of attraction. The two methods are then compared on a set of well-known test problems.     

Two constructions of oriented matroids with disconnected extension space

The extension space ℰ(ℳ) of an oriented matroid ℳ is the poset of all one-element extensions of ℳ, considered as a simplicial complex. We present two different constructions leading to rank 4 oriented matroids with disconnected extension space. We prove especially that if an elementf is not contained in any mutation of a rank 4 oriented matroid ℳ, then ℰ(ℳ\f) contains an isolated point. A uniform nonrealizable arrangement of pseudoplanes with this property is presented. The examples described contrast results of Sturmfels and Ziegler [12] who proved that for rank 3 oriented matroids the extension space has the homotopy type of the 2-sphere.     

Two noniterative algorithms for computing posteriors

In this paper, we first propose a noniterative sampling method to obtain an i.i.d. sample approximately from posteriors by combining the inverse Bayes formula, sampling/importance resampling and posterior mode estimates. We then propose a new exact algorithm to compute posteriors by improving the PMDA-Exact using the sampling-wise IBF. If the posterior mode is available from the EM algorithm, then these two algorithms compute posteriors well and eliminate the convergence problem of Markov Chain Monte Carlo methods. We show good performances of our methods by some examples.     

Two algorithms for the exchange lemma

Numerical Algorithms - In this note, we present two new algorithms for the Steinitz Exchange Lemma. They are grounded on a single application of a procedure (finding either a row echelon form or a...     

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.     

A composition for matroids

The composition of a quotient matroid Q over a collection of component matroids f₁, …, f_n indexed on the cells of Q, is described. This composition, called quotient composition, may be viewed as an application of clutter composition to matroids, or as a generalization of matroid direct sum composition to the next higher connectivity. It may also be viewed as equivalent to compositions described by Minty in 1966, and Brylawski in 1971.Quotient composition is characterized, and the circuits and rank function of a composed matroid are given. Various other properties are described, along with a category for quotient composition.     

Axioms for infinite matroids

We give axiomatic foundations for infinite matroids with duality, in terms of independent sets, bases, circuits, closure and rank. Continuing work of Higgs and Oxley, this completes the solution to a problem of Rado of 1966.     

A decomposition theory for matroids. II. Minimal violation matroids

Two decomposition theorems of Part I are utilized to characterize minimal violation matroids of matroid properties that possess certain composition and extension properties. Graphicness, planarity, and regularity have all or almost all of the desired composition and extension properties, and rather simple arguments produce the well-known minimal violation matroids.     

Two algorithms for the Student-Project Allocation problem

We study the Student-Project Allocation problem (SPA), a generalisation of the classical Hospitals/Residents problem (HR). An instance of SPA involves a set of students, projects and lecturers. Each project is offered by a unique lecturer, and both projects and lecturers have capacity constraints. Students have preferences over projects, whilst lecturers have preferences over students. We present two optimal linear-time algorithms for allocating students to projects, subject to the preference and capacity constraints. In particular, each algorithm finds a stable matching of students to projects. Here, the concept of stability generalises the stability definition in the HR context. The stable matching produced by the first algorithm is simultaneously best-possible for all students, whilst the one produced by the second algorithm is simultaneously best-possible for all lecturers. We also prove some structural results concerning the set of stable matchings in a given instance of SPA. The SPA problem model that we consider is very general and has applications to a range of different contexts besides student-project allocation.     

Two algorithms for two-phase Stefan type problems

In this paper,the relaxation algorithm and two Uzawa type algorithms for solving discretized variational inequalities arising from the two-phase Stefan type problem are proposed.An analysis of their convergence is presented and the upper bounds of the convergence rates are derived.Some numerical experiments are shown to demonstrate that for the second Uzawa algorithm which is an improved version of the first Uzawa algorithm,the convergence rate is uniformly bounded away from 1 if τh^-2 is kept bounded,where τ is the time step size and h the space mesh size.     

Two algorithms for a plant-storehouse location problem

Summary This paper considers the following assignment problem. There are some groups of plants, each group producing a different commodity. There are some consumption areas, each containing a number of storehouses and wanting a certain amount of all the commodities. The problem consists of finding the assignment of storehouses to plants which minimizes the overall cost, consisting of fixed charges associated to all storehouses and plants, and of transportation costs. For the solution of this problem, which can be called a plant-storehouse location problem, two algorithms are presented. The first algorithm makes use of a branch and bound technique; the second is based on a decomposition technique, which follows directly from the Dynamic Programming.The classic plant location problem is a particular case of the problem discussed in this paper.

---

Zusammenfassung In dieser Arbeit wird folgendes Zuordnungsproblem untersucht. Gegeben sind einige Fabrikgruppen, die jeweils verschiedene Waren herstellen, und einige Verbrauchsgebiete mit jeweils einer Anzahl von Lägern und einem bestimmten Bedarf an diesen Waren. Gesucht ist eine gesamtkostenminimale Zuordnung der Läger zu den Fabriken. Die Gesamtkosten setzen sich aus den Transportkosten und fixed charges für jede Fabrik und jedes Lager zusammen. Für dieses spezielle Standortproblem werden zwei Algorithmen entwickelt. Während der erste Algorithmus auf der Branch and Bound-Technik aufbaut, basiert der zweite auf einer aus der dynamischen Optimierung entwickelten Dekompositionstechnik.Das klassische Standorproblem ist ein Sonderfall des in dieser Arbeit behandelten Problems.

---

---

Deutsche Übersetzung:Zwei Algorithmen zur Lösung von Fabrik-Lagerhaus-Standortproblemen.

---

This work has been supported by Consiglio Nazionale delle Ricerche (C. N. R.), Roma, Italy.

---

The authors are with the Istituto di Elettrotecnica ed Elettronica, Laboratorio di Controlli Automatici, Politecnico di Milano, Milano, Italy.     

Wei-type duality theorems for matroids

We present several fundamental duality theorems for matroids and more general combinatorial structures. As a special case, these results show that the maximal cardinalities of fixed-ranked sets of a matroid determine the corresponding maximal cardinalities of the dual matroid. Our main results are applied to perfect matroid designs, graphs, transversals, and linear codes over division rings, in each case yielding a duality theorem for the respective class of objects.     

Separation theorems for oriented matroids

In this paper we show that Minty's lemma can be used to prove the Hahn-Banach theorem as well as other theorems in this class such as Radon's and Helly's theorem for oriented matroids having an intersection property which guarantees that every pair of flats intersects in some point extension p of the oriented matroid .