Structural analysis of a fractional matching problem

Mixed Software Programming refers to a novel software development paradigm resulting from efforts to combine two different programming approaches: Solo Programming and Pair Programming. Solo Programming refers to the traditional practice of assigning a single developer to develop a software module and Pair Programming refers to a relatively new approach where two developers work simultaneously on developing a module. In Mixed Programming, given a set of modules to be developed, a chosen subset of modules may be developed using Solo Programming and the remaining modules using Pair Programming.Motivated by applications in Mixed Software Programming, we consider the following generalization of classical fractional 1-matching problem: Given an undirected simple graph G=(V;E), and a positive number F, find values for x_e,e∈E, satisfying the following:

1.

.

2.

, where δ(i)={e∈E:e=(i,j)},i∈V.

3.

Maximize {2∑_e∈Ex_e−F|{i∈V:∑_e∈δ(i)x_e=1}|}.

We show that this problem is solvable in strongly polynomial time. Our primary focus in this paper is on obtaining the structure of the optimal solution for an arbitrary instance of the problem.