On a discrete optimization problem

Abstract

In this paper we are concerned with the following optimization problem: given a matroid on a finite set E and w ₁,w ₂ two real weight function on E, find a base B ₀ minimizing w ₁(B) + √w ₂(B) on the family of all basis B of the matroid (w _i (B) = Σ _e∈B w _i (e)i = 1, 2; w ₂(B) > 0). The problem is motivated by a stochastic version of the well-known minimum weight basis problem. An efficient algorithm for solving this problem, which combine a search procedure with the greedy algorithm is given.

Keywords:

• Matroid optimization
• stochastic optimization
• search procedures

C.R.Categories:

• G.2.2
• F.2.2