Balancedness Issues And Algorithms On Edge Covering Games

Combinatorial cooperative game, also named as combinatorial optimizationgame, is proposed to model the profit or cost allocation problem which arises fromsome combinatorial optimization problems. Cooperative game theory considershow to distribute the total income (or cost) generated by a group to its membersfairly and rationally. The core is one of the most important solution concepts,which is defined on the basis of subgroup rationality. The game is called balancedif its core is nonempty. In this thesis, we focus on some cooperative game modelsarising from edge covering problems on graphs. We consider the balancedness ofthe games, and discuss the algorithmic issues on their cores. The main resultsare as follows:(1) Two related cooperative games arising from integer edge covering prob-lems on graphs, relaxed and rigid {k}-edge covering games, are introduced; basedon a new program formulation for integer edge covering problem and duality the-ory, a common necessary and su?cient condition for the balancedness of bothgames is obtained; moreover, algorithmic issues on cores are discussed.(2) Two related cooperative games arising from fractional edge coveringproblems on graphs, relaxed and rigid fractional edge covering games, are alsointroduced. With duality theory of linear programming, we prove that bothgames are balanced, and give the relationship between their cores.