Structural analysis of a fractional matching problem |
| |
Authors: | R Chandrasekaran |
| |
Institution: | a Department of Computer Science, University of Texas at Dallas, United States b School of Management, University of Texas at Dallas, United States |
| |
Abstract: | 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 xe,e∈E, satisfying the following: - 1.
.- 2.
, where δ(i)={e∈E:e=(i,j)},i∈V.- 3.
- Maximize {2∑e∈Exe−F|{i∈V:∑e∈δ(i)xe=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. |
| |
Keywords: | Matching Mixed software programming Structural analysis |
本文献已被 ScienceDirect 等数据库收录! |
|