RO EN
An approximation algorithm for matroids with coalitions. (English)
Authors: Zelikovsky A. Z.
Abstract
Given a family $P$ of pairwise disjoint independent sets (called coalitions) in a matroid $M=(X,I,d)$ with independence system $I$ and additivec weith function $d:2^X\Rightarrow R^+$, let $d_p:2^X \Rightarrow R^+$ be a weitht function such that $d_p|_X=d|_X$ and for any $A\subseteq X$, $d_p(A)=\Sigma \{d_p(\pi ) | \pi \in A_p\}+ d(A\setminus U\{\pi |\pi \in A_p\})\le d(A)$, where $A_p=\{\pi | \pi \le A\varepsilon \pi \in P\}$. We represent an approximation algorithm for the $NP$-hard problem of finding a minimum weitht base in a matroid with coalitions.Contents
- Countably compact topologies on Boolean rings. (Russian)
- Locally dissipative dynamical systems and some of their applications. (Russian)
- Conditions for the maximal multiplicity of an integral line of a differential system with homogeneities of $m$th order. (Russian)
- On the spectrum in the right half-plane of a class of operator pencils. (Russian)
- K-loops. (Russian)
- Groups of automorphisms of medial quasigroups and medial fields. (Russian)
- On the spectrum of perturbed differential operators with periodic coefficients. (Russian)
- Parametric completeness in the logic of the simplest pseudo-Boolean algebra with incomparable elements. (Russian)
- Coefficient conditions for the coexistence of two singular points of summed multiplicity 4 in a finite part of a phase plane of a quadratic system. (Russian)
- On the kinds of two-dimensional multiregular partitions. (Russian)
- On a class of nonlocal generalized splines. (Russian)
- On the number of near neighbors in regular partitions of Lobachevskij space by compact polyhedra. (Russian)
- An approximation algorithm for matroids with coalitions. (English)
- On finite projection of nonstationary $M/GI/1$ queueing systems. (English)
- Numerical modeling of the process of high-velocity penetration of an obstacle. (Russian)
