New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems. (English) Zbl 0844.90067

Barvinok, Alexander I.

Math. Program. 69, No. 3 (A), 449-470 (1995).

Summary: We present algorithms for the \(k\)-Matroid Intersection Problem and for the Matroid \(k\)-Parity Problem when the matroids are represented over the field of rational numbers and \(k > 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 the \(k\)-Dimensional Assignment Problem and of the \(k\)-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 for \(k = 2\).

MSC:

90C27	Combinatorial optimization
05B35	Combinatorial aspects of matroids and geometric lattices

Keywords:

\(k\)-matroid intersection problem; matroid \(k\)-parity problem; \(k\)-dimensional assignment problem; \(k\)-dimensional matching problem; hyperdeterminant

References:

[1]	A.V. Aho, J.E. Hopcroft and J.D. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974). · Zbl 0326.68005
[2]	A.I. Barvinok, ”Optimization problems on matroids and exponential sums,” in: E. Balas, G. Cornuéjols and R. Kannan, eds.,Integer Programming and Combinatorial Optimization, Proceedings of the Second IPCO Conference, Carnegie Mellon University (1992) pp. 316–333.
[3]	P.M. Camerini, G. Galbiati and F. Maffioli, ”Random pseudo-polynomial algorithms for exact matroid problems,”Journal of Algorithms 13 (1992) 258–273. · Zbl 0773.05032 · doi:10.1016/0196-6774(92)90018-8
[4]	A. Cayley, ”On the theory of determinants,” in:Collected Papers, Vol. 1 (Cambridge University Press, Cambridge, 1889) pp. 63–80. · JFM 20.0140.01
[5]	A. Cayley, ”On the theory of linear transformations,” in:Collected Papers, Vol. 1 (Cambridge University Press, Cambridge, 1889) pp. 80–94. · JFM 20.0140.01
[6]	G. Galbiati and F. Maffioli, ”On the computation of pfaffians,”Discrete Applied Mathematics 51 (1994) 269–275. · Zbl 0811.68083 · doi:10.1016/0166-218X(92)00034-J
[7]	M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-completeness (Freeman, San Francisco, CA, 1979). · Zbl 0411.68039
[8]	F. Harary,Graph Theory (Addison-Wesley, Reading, MA, 1969).
[9]	E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976). · Zbl 0413.90040
[10]	L. Lovász, ”On determinants, matchings and random algorithms,” in: L. Budach, ed.,Fundamentals of Computation Theory, Proceedings of the Conference on Algebraic, Arithmetic and Categorial Methods in Computation Theory (Akademie-Verlag, Berlin, 1979) pp. 565–574. · Zbl 0446.68036
[11]	L. Lovász, ”The matroid matching problem,” in: L. Lovász and V.T. Sós, eds.,Algebraic Methods in Graph Theory (North-Holland, Amsterdam, 1981) pp. 495–517. · Zbl 0478.05027
[12]	L. Lovász and M.D. Plummer,Matching Theory (Akadémia Kiadò, Budapest/North-Holland, Amsterdam, 1986).
[13]	I. Satake,Linear Algebra (Marcel Dekker, New York, 1975).
[14]	Yu.G. Smetanin and L.G. Khachiyan, ”Use of pseudopolynomial algorithms for some problems of combinatorial optimization with constraints,”Izvestiya Akademii Nauk SSSR Tekhnicheskaya Kibernetika (6) (1986) 139–144 (in Russian); translated in:Soviet Journal of Computer and Systems Science 25 (2) (1987) 161–165.
[15]	N.P. Sokolov,Spatial Matrices and their Applications (Fizmatgiz, Moscow, 1960, in Russian).
[16]	D.J.A. Welsh,Matroid Theory (Academic Press, London, 1976).