Results 31 to 40 of about 4,343 (225)
Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search [PDF]
, 2013 We present an optimal, combinatorial 1−1/e approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm (Calinescu, Chekuri, Pál and Vondrák, 2008), our algorithm is extremely simple ...
Filmus, Yuval +3 more
core +1 more source
European Journal of Combinatorics, 2011 We introduce and study a natural variant of matroid amalgams. For matroids M(A) and N(B) such that M/(A-B)=N(B-A), we define a splice of M and N to be a matroid L on the union of A and B with L(B-A)=M and L/(A-B)=N. We show that splices exist for each such pair of matroids M and N; furthermore, there is a freest splice of M and N, which we call the ...
Joseph E. Bonin, William R. Schmitt
openaire +3 more sources
Hierarchical Zonotopal Power Ideals [PDF]
Discrete Mathematics & Theoretical Computer Science, 2011 Zonotopal algebra deals with ideals and vector spaces of polynomials that are related to several combinatorial and geometric structures defined by a finite sequence of vectors.
Matthias Lenz
doaj +1 more source
The Electronic Journal of Combinatorics, 2006 One way to choose a basis of a matroid at random is to choose an ordering of the ground set uniformly at random and then use the greedy algorithm to find a basis. We investigate the class of matroids having the property that this procedure yields a basis uniformly at random.
openaire +2 more sources
Phase Transition as an Emergent Phenomenon Analysed by Violation of Structural Invariant (M, BM)
Mendel, 2020 When modeling complex systems, we usually encounter the following difficulties: partiality, large amounts of data and uncertainty of conclusions. The most common approach used for modeling is the physical approach, sometimes reinforced by statistical ...
Jiri Bila, Ali H Reshak, Jan Chysky
doaj +1 more source
New light on Bergman complexes by decomposing matroid types [PDF]
Discrete Mathematics & Theoretical Computer Science, 2012 Bergman complexes are polyhedral complexes associated to matroids. Faces of these complexes are certain matroids, called matroid types, too. In order to understand the structure of these faces we decompose matroid types into direct summands.
Martin Dlugosch
doaj +1 more source
Matroid Secretary for Regular and Decomposable Matroids [PDF]
SIAM Journal on Computing, 2013 In the matroid secretary problem we are given a stream of elements and asked to choose a set of elements that maximizes the total value of the set, subject to being an independent set of a matroid given in advance. The difficulty comes from the assumption that decisions are irrevocable: if we choose to accept an element when it is presented by the ...
Michael Dinitz, Guy Kortsarz
openaire +2 more sources
Applications of Matrices to a Matroidal Structure of Rough Sets
Journal of Applied Mathematics, 2013 Rough sets provide an efficient tool for dealing with the vagueness and granularity in information systems. They are widely used in attribute reduction in data mining. There are many optimization issues in attribute reduction.
Jingqian Wang, William Zhu
doaj +1 more source
A lattice point counting generalisation of the Tutte polynomial [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 The Tutte polynomial for matroids is not directly applicable to polymatroids. For instance, deletion- contraction properties do not hold. We construct a polynomial for polymatroids which behaves similarly to the Tutte polynomial of a matroid, and in fact
Amanda Cameron, Alex Fink
doaj +1 more source
European Journal of Combinatorics, 2017 A laminar family is a collection $\mathscr{A}$ of subsets of a set $E$ such that, for any two intersecting sets, one is contained in the other. For a capacity function $c$ on $\mathscr{A}$, let $\mathscr{I}$ be $\{I:|I\cap A| \leq c(A)\text{ for all $A\in\mathscr{A}$}\}$.
Tara Fife, James G. Oxley
openaire +2 more sources