in black and white
Main menu
Share a book About us Home
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics

Combinatorial Optimization - Cristofides N.

Cristofides N. Combinatorial Optimization - Wiley publishing , 2012. - 212 p.
Download (direct link): Ņombinatorialoptimi2012.pdf
Previous << 1 .. 51 52 53 54 55 56 < 57 > 58 59 60 61 62 63 .. 156 >> Next

Set Partitioning—A Survey 155
On the other hand, sp is a special case of spp; conversely, spp can be restated as
max {dm + c"x | Ax e, x,- = 0 or 1, j e N}
with c" = 0eA—c; and again, for d sufficiently large, this problem has the same set of optimal solutions as spp, whenever the latter is feasible.
The equivalence of sp and spp is crucial to some of the results to be discussed.
Next we turn to a family of four interrelated problems defined on an undirected graph, two of which are special cases of sp.
7.1.3 Edge Matching and Covering, Node Packing and Covering
Let G = (N, E) be a finite undirected graph with n = |N| nodes and q = |E| edges. Let Aa be the n 'x q node-edge incidence matrix of G, en, and eQ the n -vector and q-vector respectively, whose components are all 1.
An edge matching in G is a subset E' of edges such that every node of G is incident with at most one edge in E'. If every node of G is incident with exactly one edge in E', then E' is a perfect matching. An edge cover (a covering of nodes by edges) in G is a subset E" of edges such that every node of G is incident with at least one edge in E". The edge matching problem, or the problem of finding a maximum-cardinality edge matching in G, is then
em max{eqy | AGy =?e„, y, =0 or 1, i = 1,. .., q}
while the edge covering problem, or the problem of finding a minimum-cardinality edge cover in G, is
ec min {eqy | A0y =5 en, y; = 0 or 1, i,..., q}.
A node packing (vertex packing) in G is a subset N' of nodes such that every edge of G is incident with at most one node in N". The node packing problem, or the problem of finding a maximum-cardinality node packing (internally stable node set, independent node set) in G, is then
np max{e„x | Ajx =? eq, x, =0 or 1, j = 1,. .., n}
while the node covering problem, or the problem of finding a minimum cardinality node cover in G, is
nc min{e„x | Ajxs* eq, x( =0 or 1, j = 1,..., rc}.
If a0, (30, <*!, and (3, are the cardinality of a maximum node packing, minimum node cover, maximum edge matching, and minimum edge cover in G, respectively, then these four numbers are connected by the following simple formula.
Egon Balas and Manfred W. Padberg
Theorem 7.1 (Gallai 1958) For any nontrivial connected graph G with n nodes,
a0 + /30 = n = a1 + /31.
A maximum edge matching and a minimum edge cover are easily obtained from each other; the same is true of a maximum node packing and a minimum node cover.
Clearly, em and np are special cases of sp. The problem of finding a perfect edge matching, obtained from em by replacing the inequality with equality, is on the other hand a special c^se of spp.
When G is bipartite, AG is totally unimodular and the four integer programs listed above can be replaced by the associated linear programs. In the general case, however, the optimal solutions to these linear programs need not be integer. On the other hand, a basic result on convex polyhedra, due to Weyl (1935), implies that there always exists a finite system of linear inequalities whose solution set is the convex hull of feasible integer points. Identifying such a defining linear system is not an easy task in general. For the edge matching problem, this task was solved by Edmonds (1965a) (see also Edmonds, 1965b), who has also given an algorithm of complexity 0(n3) for solving em or its weighted version (in which eq is replaced by an arbitrary integer vector), based on Berge’s (1957) theorem of alternating chains and using the above mentioned defining linear system to prove optimality (for related work see also Balinski, 1969, 1972).
More recently, Pulleyblank and Edmonds (1973) have sharpened the characterization of the edge mathing polytdpe by identifying its (unique) minimal defining linear system.
An optimal solution to em also (trivially) yields an optimal solution to ec.
The pair of problems np, nc, is considerably more difficult. Balinski (1969) has characterized maximum node packings in terms of alternating subgraphs (see also Edmonds, 1962), but no polynomially bounded algorithm is known for the solution of this problem. More recently, several classes of facets of the node packing polytope have been identified (see Padberg, 1971, 1973a, 1975b; Chvatal, 1972; Nemhauser and Trotter, 1974; Trotter, 1974; Balas and Zemal, 1976a,b). Some algorithms have also been proposed (see Trotter, 1973; Balas and Samuelsson, 1973, 1974a), none of which is polynomially bounded.
7.1.4 Node Packing, Set Packing, Clique Covering
Denote by at the ;th column of the matrix A of sp. The intersection graph Ga = (N, E) of A has one node for every column of A, and one edge for every pair of nonorthogonal columns of A [i.e. (i,j)eE if and only if OiOj 1]. Let Aa be the node-edge incidence matrix of GA, and denote by
Set Partitioning—A Survey
np the weighted node packing problem whose weights c, are the same for each node as those of sp, i.e.
np max {cx | Aj x =? eq, x, = 0 or 1, j = 1, . .., n}.
Remark 7.1 x is a feasible (optimal) solution to sp if and only if it is a feasible (optimal solution to np.
Previous << 1 .. 51 52 53 54 55 56 < 57 > 58 59 60 61 62 63 .. 156 >> Next