ISSN:
1436-4646
Keywords:
Matroid intersection problem
;
Fenchel duality
;
Convex analysis
;
Combinatorial optimization
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The weighted matroid intersection problem has recently been extended to the valuated matroid intersection problem: Given a pair of valuated matroidsM i = (V, ℬ i , ω i ) (i = 1,2) defined on a common ground setV, find a common baseB ∈ ℬ 1 ∩ ℬ 2 that maximizesω 1 (B) + ω 2 (B). This paper develops a Fenchel-type duality theory related to this problem with a view to establishing a convexity framework for nonlinear integer programming. A Fenchel-type min max theorem and a discrete separation theorem are given. Furthermore, the subdifferentials of matroid valuations are investigated. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01580075
Permalink
