Integer Programming and Combinatorial Optimization

In this paper we explore the geometry of the integer points in a cone rooted at a rational point. This basic geometric object allows us to establish some links between lattice point free bodies and the derivation of inequalities for mixed integer linear programs by considering two rows of a simplex tableau simultaneously.

A conic integer program is an integer programming problem with conic constraints. Conic integer programming has important applications in finance, engineering, statistical learning, and probabilistic integer programming.

Here we study mixed-integer sets defined by second-order conic constraints. We describe general-purpose conic mixed-integer rounding cuts based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve continuous conic programming relaxations at the nodes of the search tree. Our preliminary computational experiments with the new cuts show that they are quite effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs.

In this paper, we show how to generate strong cuts for unstructured mixed integer programs through the study of high-dimensional group problems. We present a new operation that generates facet-defining inequalities for two-dimensional group problems by combining two facet-defining inequalities of one-dimensional group problems. Because the procedure allows the use of a large variety of one-dimensional constituent inequalities, it yields large families of new cutting planes for MIPs that we call

sequential-merge inequalities

. We show that sequential-merge inequalities can be used to generate inequalities whose continuous variable coefficients are stronger than those of one-dimensional cuts and can be used to derive the three-gradient facet-defining inequality introduced by Dey and Richard [4].

A

simple 2-matching

in an edge-weighted graph is a subgraph all of whose vertices have degree 1 or 2. We consider the problem of finding a maximum weight simple 2-matching that contains no triangles, which is closely related to a class of relaxations of the TSP. Our main results are, for graphs with maximum degree 3, a complete description of the convex hull of incidence vectors of triangle-free simple 2-matchings and a strongly polynomial time algorithm for the above problem. Our system requires the use of a type of comb inequality (introduced by Grötschel and Padberg for the TSP polytope) that has {0,1,2}-coefficients and hence is more general than the well-known blossom inequality used in Edmonds’ characterization of the simple 2-matching polytope.

A well established heuristic approach for solving various bicriteria optimization problems is to enumerate the set of Pareto optimal solutions, typically using some kind of dynamic programming approach. The heuristics following this principle are often successful in practice. Their running time, however, depends on the number of enumerated solutions, which can be exponential in the worst case.

In this paper, we prove an almost tight bound on the expected number of Pareto optimal solutions for general bicriteria integer optimization problems in the framework of smoothed analysis. Our analysis is based on a semi-random input model in which an adversary can specify an input which is subsequently slightly perturbed at random, e. g., using a Gaussian or uniform distribution.

Our results directly imply tight polynomial bounds on the expected running time of the Nemhauser/Ullmann heuristic for the 0/1 knapsack problem. Furthermore, we can significantly improve the known results on the running time of heuristics for the bounded knapsack problem and for the bicriteria shortest path problem. Finally, our results also enable us to improve and simplify the previously known analysis of the smoothed complexity of integer programming.

We show that one can compute a (simple) polytope from its graph in Polynomial time. This computation of a polytope from its graph was shown to be solvable by Blind and Mani and more recently Kalai provided a simple proof that leads to an exponential time algorithm. Our proof relies on a Primal-Dual characterization by Joswig, Kaibel and Korner. We describe an exponential Linear Programming which can be used to construct the solution and show that it can be solved in polynomial time.

The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the order of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up the branch-and-cut tree.

We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving such symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the branch-and-cut tree, removes redundant parts of the tree produced by the above mentioned symmetry. The method relies on certain polyhedra, called orbitopes, which have been investigated in [11]. It does, however, not add inequalities to the model, and thus, it does not increase the difficulty of solving the linear programming relaxations. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem motivated from frequency planning in mobile telecommunication networks.

We discuss an open source implementation and preliminary computational testing of three variants of the Balas-Perregaard procedure for generating lift-and-project cuts from the original simplex tableau, two of which are new. Variant 1 is the original procedure of [6] with minor modifications. Variant 2 uses a new procedure for choosing the pivot element: After identifying the set of row candidates for an improving pivot, the pivot element (and column) is chosen by optimizing over the entries of all candidate rows. Finally, Variant 3 replaces the source row with its disjunctive modularization, and after each pivot it again modularizes the resulting source row. We report on computational results with the above three variants and their combinations on 65 MIPLIB.3 instances.

We introduce

orbital branching

, an effective branching method for integer programs containing a great deal of symmetry. The method is based on computing groups of variables that are equivalent with respect to the symmetry remaining in the problem after branching, including symmetry which is not present at the root node. These groups of equivalent variables, called orbits, are used to create a valid partitioning of the feasible region which significantly reduces the effects of symmetry while still allowing a flexible branching rule. We also show how to exploit the symmetries present in the problem to fix variables throughout the branch-and-bound tree. Orbital branching can easily be incorporated into standard IP software. Through an empirical study on a test suite of symmetric integer programs, the question as to the most effective orbit on which to base the branching decision is investigated. The resulting method is shown to be quite competitive with a similar method known as

isomorphism pruning

and significantly better than a state-of-the-art commercial solver on symmetric integer programs.

Erdős, Purdy, and Straus conjectured that the number of distinct (nonzero) areas of the triangles determined by

n

noncollinear points in the plane is at least

$\lfloor \frac{n-1}{2} \rfloor$

, which is attained for ⌈

n

/ 2⌉ and respectively

$\lfloor n/2\rfloor$

equally spaced points lying on two parallel lines. We show that this number is at least

$\frac{17}{38}n -O(1) \approx 0.4473n$

. The best previous bound,

$(\sqrt{2}-1)n-O(1)\approx 0.4142n$

, which dates back to 1982, follows from the combination of a result of Burton and Purdy [5] and Ungar’s theorem [23] on the number of distinct directions determined by

n

noncollinear points in the plane.

We consider the single machine scheduling problem to minimize the average weighted completion time under precedence constrains. Improving on the various 2-approximation algorithms is considered one of the ten most prominent open problems in scheduling theory. Recently, research has focused on special cases of the problem, mostly by restricting the set of precedence constraints to special classes such as convex bipartite, two-dimensional, and interval orders.

In this paper we extend our previous results by presenting a framework for obtaining (2 − 2/

d

)-approximation algorithms provided that the set of precedence constraints has fractional dimension

d

. Our generalized approach yields the best known approximation ratios for all previously considered classes of precedence constraints, and it provides the first results for bounded degree and interval dimension 2 orders.

As a negative result we show that the addressed problem remains NP-hard even when restricted to the special case of interval orders.

There has been a series of results deriving approximation algorithms for 2-stage discrete stochastic optimization problems, in which the probabilistic component of the input is given by means of “black box”, from which the algorithm “learns” the distribution by drawing (a polynomial number of ) independent samples. The performance guarantees proved for such problems, of course, is generally worse than for their deterministic analogue. We focus on a 2-stage stochastic generalization of the problem of finding the maximum-weight subset of jobs that can be scheduled on one machine where each job is constrained to be processed within a specified time window. Surprisingly, we show that for this generalization, the same performance guarantee that is obtained for the deterministic case can be obtained for its stochastic extension.

Our algorithm builds on an approach of Charikar, Chekuri, and Pál: one first designs an approximation algorithm for the so-called polynomial scenario model (in which the probability distribution is restricted to have the property that there are only a polynomial number of possible realizations of the input that occur with positive probability); then one shows that by sampling from the distribution via the “black box” to obtain an approximate distribution that falls in this class and approximately solves this approximation to the problem, one nonetheless obtains a near-optimal solution to the original problem. Of course, to follow this broad outline, one must design an approximation algorithm for the stochastic optimization problem in the polynomial scenario model, and we do this by extending a result of Bar-Noy, Bar-Yehuda, Freund, Naor, and Schieber.

Furthermore, the results of Bar-Noy et al. extend to a wide variety of resource-constrained selection problems including, for example, the unrelated parallel-machine generalization

R

|

r

j

| ∑ 

w

j

U

j

and point-to-point admission control routing in networks (but with a different performance guarantee). Our techniques can also be extended to yield analogous results for the 2-stage stochastic generalizations for this class of problems.

Consider an integer program max (

c

t

x

:

Ax

 = 

b

,

x

 ≥ 0,

x

 ∈ 

Z

n

) where

A

 ∈ 

Z

m

×

n

,

b

 ∈ 

Z

m

, and

c

 ∈ 

Z

n

. We show that the integer program can be solved in pseudo-polynomial time when

A

is non-negative and the column-matroid of

A

has constant branch-width.

According to the present state of the theory of the matroid matching problem, the existence of a good characterization to the size of a maximum matching depends on the behavior of certain substructures, called double circuits. In this paper we prove that if a polymatroid has no double circuits at all, then a partition-type min-max formula characterizes the size of a maximum matching. We provide applications of this result to parity constrained orientations and to a rigidity problem.

A polynomial time algorithm is constructed by generalizing the principle of shrinking blossoms used in Edmonds’ matching algorithm [2].

Let

$f:2^{N} \rightarrow \cal R^{+}$

be a non-decreasing submodular set function, and let

$(N,\cal I)$

be a matroid. We consider the problem

$\max_{S \in \cal I} f(S)$

. It is known that the greedy algorithm yields a 1/2-approximation [9] for this problem. It is also known, via a reduction from the max-

k

-cover problem, that there is no (1 − 1/

e

 + 

ε

)-approximation for any constant

ε

> 0, unless

P

 = 

NP

[6]. In this paper, we improve the 1/2-approximation to a (1 − 1/

e

)-approximation, when

f

is a sum of weighted rank functions of matroids. This class of functions captures a number of interesting problems including set coverage type problems. Our main tools are the pipage rounding technique of Ageev and Sviridenko [1] and a probabilistic lemma on monotone submodular functions that might be of independent interest.

We show that the generalized assignment problem (GAP) is a special case of our problem; although the reduction requires |

N

| to be exponential in the original problem size, we are able to interpret the recent (1 − 1/

e

)-approximation for GAP by Fleischer

et al.

[10] in our framework. This enables us to obtain a (1 − 1/

e

)-approximation for variants of GAP with more complex constraints.

We study the Master Equality Polyhedron (MEP) which generalizes the Master Cyclic Group Polyhedron and the Master Knapsack Polyhedron.

We present an explicit characterization of the nontrivial facet-defining inequalities for MEP. This result generalizes similar results for the Master Cyclic Group Polyhedron by Gomory [9] and for the Master Knapsack Polyhedron by Araoz [1]. Furthermore, this characterization also gives a polynomial time algorithm for separating an arbitrary point from the MEP.

We describe how facet defining inequalities for the Master Cyclic Group Polyhedron can be lifted to obtain facet defining inequalities for the MEP, and also present facet defining inequalities for the MEP that cannot be obtained in such a way. Finally, we study the mixed-integer extension of the MEP and present an interpolation theorem that produces valid inequalities for general Mixed Integer Programming Problems using facets of the MEP.

In this paper, we present a systematic method to derive strong superadditive approximations of multidimensional lifting functions using single-dimensional superadditive functions. This constructive approach is based on the observation that, in many cases, the lifting function of a multidimensional problem can be expressed or approximated through the single-dimensional lifting function of some of its components. We then apply our approach to two variants of classical models and show that it yields an efficient procedure to derive strong valid inequalities.

During the last decades, much research has been conducted deriving classes of valid inequalities for single-row mixed integer programming polyhedrons. However, no such class has had as much practical success as the MIR inequality when used in cutting plane algorithms for general mixed integer programming problems. In this work we analyze this empirical observation by developing an algorithm which takes as input a point and a single-row mixed integer polyhedron, and either proves the point is in the convex hull of said polyhedron, or finds a separating hyperplane. The main feature of this algorithm is a specialized subroutine for solving the Mixed Integer Knapsack Problem which exploits cost and lexicographic dominance. Separating over the entire closure of single-row systems allows us to establish natural benchmarks by which to evaluate specific classes of knapsack cuts. Using these benchmarks on Miplib 3.0 instances we analyze the performance of MIR inequalities. Computations are performed in exact arithmetic.

We consider the problem of minimizing a submodular function

f

defined on a set

V

with

n

elements. We give a combinatorial algorithm that runs in O(

n

5

EO +

n

6

) time, where EO is the time to evaluate

f

(

S

) for some

S

⊆

V

. This improves the previous best strongly polynomial running time by more than a factor of

n.

This note considers convex optimization problems over base polytopes of polymatroids. We show that the decomposition algorithm for the separable convex function minimization problems helps us give simple sufficient conditions for the rationality of optimal solutions and that it leads us to some interesting properties, including the equivalence of the lexicographically optimal base problem, introduced by Fujishige, and the submodular utility allocation market problem, introduced by Jain and Vazirani. In addition, we develop an efficient implementation of the decomposition algorithm via parametric submodular function minimization algorithms. Moreover, we show that, in some remarkable cases, non-separable convex optimization problems over base polytopes can be solved in strongly polynomial time.

This paper presents an efficient algorithm for minimizing a certain class of submodular functions that arise in analysis of multiclass queueing systems. In particular, the algorithm can be used for testing whether a given multiclass M/M/1 achieves an expected performance by an appropriate control policy. With the aid of the topological sweeping method for line arrangement, our algorithm runs in

O

(

n

2

) time, where

n

is the cardinality of the ground set. This is much faster than direct applications of general submodular function minimization algorithms.

As mixed integer programming (MIP) problems become easier to solve in pratice, they are used in a growing number of applications where producing a unique optimal solution is often not enough to answer the underlying business problem. Examples include problems where some optimization criteria or some constraints are difficult to model, or where multiple solutions are wanted for quick solution repair in case of data changes. In this paper, we address the problem of effectively generating multiple solutions for the same model, concentrating on optimal and near-optimal solutions. We first define the problem formally, study its complexity, and present three different algorithms to solve it. The main algorithm we introduce, the one-tree algorithm, is a modification of the standard branch-and-bound algorithm. Our second algorithm is based on MIP heuristics. The third algorithm generalizes a previous approach that generates solutions sequentially. We then show with extensive computational experiments that the one-tree algorithm significantly outperforms previously known algorithms in terms of the speed to generate multiple solutions, while providing an acceptable level of diversity in the solutions produced.

In this paper we present a method for finding exact solutions of the Max-Cut problem max

x

T

Lx

such that

x

 ∈ { − 1,1}

n

. We use a semidefinite relaxation combined with triangle inequalities, which we solve with the bundle method. This approach is due to [12] and uses Lagrangian duality to get upper bounds with reasonable computational effort. The expensive part of our bounding procedure is solving the basic semidefinite programming relaxation of the Max-Cut problem.

We review other solution approaches and compare the numerical results with our method. We also extend our experiments to unconstrained quadratic 0-1 problems and to instances of the graph bisection problem.

The experiments show, that our method nearly always outperforms all other approaches. Our algorithm, which is publicly accessible through the Internet, can solve virtually any instance with about 100 variables in a routine way.

We introduce DISTANCE INDUCED NEIGHBOURHOOD SEARCH (DINS), aMIP improvement heuristic that tries to find improved MIP feasible solutions from a givenMIP feasible solution. DINS is based on a variation of local search that is embedded in an exact MIP solver, namely a branch-and-bound or a branch-and-cut MIP solver. The key idea is to use a distancemetric between the linear programming relaxation optimal solution and the currentMIP feasible solution to define search neighbourhoods at different nodes of the search tree generated by the exact solver. DINS considers each defined search neighbourhood as a new MIP problem and explores it by an exact MIP solver with a certain node limit. On a set of standard benchmark problems, DINS outperforms the MIP improvement heuristics Local Branching due to Fischetti and Lodi and Relaxation Induced Neighbourhood Search due to Danna, Rothberg, and Pape, as well as the generic commercial MIP solver Cplex.

Let

A

be the edge-node incidence matrix of a bipartite graph

G

 = (

U

,

V

;

E

),

I

be a subset of the nodes of

G

, and

b

be a vector such that 2

b

is integral. We consider the following mixed-integer set:

$$X(G,b,I)=\{x\,:\,Ax\geq b,\,x\geq 0,\,x_i\mbox{ integer for all }i\in I\}.$$

We characterize conv(

X

(

G

,

b

,

I

)) in its original space. That is, we describe a matrix (

C

,

d

) such that conv(

X

(

G

,

b

,

I

)) = {

x

:

Cx

 ≥ 

d

}. This is accomplished by computing the projection onto the space of the

x

-variables of an extended formulation, given in [1], for conv(

X

(

G

,

b

,

I

)). We then give a polynomial-time algorithm for the separation problem for conv(

X

(

G

,

b

,

I

)), thus showing that the problem of optimizing a linear function over the set

X

(

G

,

b

,

I

) is solvable in polynomial time.

We study the mixed-integer rounding (MIR) closure of polyhedra. The MIR closure of a polyhedron is equal to its split closure and the associated separation problem is NP-hard. We describe a mixed-integer programming (MIP) model with linear constraints and a non-linear objective for separating an arbitrary point from the MIR closure of a given mixed-integer set. We linearize the objective using additional variables to produce a linear MIP model that solves the separation problem approximately, with an accuracy that depends on the number of additional variables used. Our analysis yields a short proof of the result of Cook, Kannan and Schrijver (1990) that the split closure of a polyhedron is again a polyhedron. We also present some computational results with our approximate separation model.

In this paper we investigate two generalizations of the continuous mixing set studied by Miller and Wolsey [5] and Van Vyve [7]: the intersection set

and the continuous mixing set with flows

which appears as a strong relaxation of some single-item lot-sizing problems. We give two extended formulations for the convex hull of each of these sets. In particular, for

X

CMF

the sizes of the extended formulations are polynomial in the size of the original description of the set, thus proving that the corresponding linear optimization problem can be solved in polynomial time.

Given

z

 ∈ ℂ

n

and

A

 ∈ ℤ

m

×

n

, we provide an explicit expression and an algorithm for evaluating the counting function

h

(

y

;

z

): = ∑ {

z

x

|

x

 ∈ ℤ

n

;

Ax

=

y

,

x

 ≥ 0}. The algorithm only involves simple (but possibly numerous) calculations. In addition, we exhibit

finitely many

fixed convex cones of ℝ

n

explicitly and exclusively defined by

A

, such that for

any

y

 ∈ ℤ

m

,

h

(

y

;

z

) is obtained by a simple formula that evaluates ∑ 

z

x

over the integral points of those cones only. At last, we also provide an alternative (and different) formula from a decomposition of the generating function into simpler rational fractions, easy to invert.

In this paper we provide new characterizing properties of TDI systems. A corollary is Sturmfels’ theorem relating toric initial ideals generated by square-free monomials to unimodular triangulations. A reformulation of these test-sets to polynomial ideals actually generalizes the existence of square-free monomials to arbitrary TDI systems, providing new relations between integer programming and Gröbner bases of toric ideals. We finally show that stable set polytopes of perfect graphs are characterized by a refined fan that is a triangulation consisting only of unimodular cones, a fact that endows the Weak Perfect Graph Theorem with a computationally advantageous geometric feature. Three ways of implementing the results are described and some experience about one of these is reported.

This paper presents a connection between qualitative matrix theory and linear complementarity problems (LCPs). An LCP is said to be

sign-solvable

if the set of the sign patterns of the solutions is uniquely determined by the sign patterns of the given coefficients. We provide a characterization for sign-solvable LCPs such that the coefficient matrix has nonzero diagonals, which can be tested in polynomial time. This characterization leads to an efficient combinatorial algorithm to find the sign pattern of a solution for these LCPs. The algorithm runs in O(

γ

) time, where

γ

is the number of the nonzero coefficients.

Linear programs with joint probabilistic constraints (PCLP) are known to be highly intractable due to the non-convexity of the feasible region. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We present a mixed integer programming formulation and study the relaxation corresponding to a single row of the probabilistic constraint, yielding two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. We present computational results that indicate that by using our strengthened formulations, large scale instances can be solved to optimality.

Consider the following Steiner Tree leasing problem. Given a graph

G

 = (

V

,

E

) with root

r

, and a sequence of terminal sets

D

t

 ⊆ 

V

for each day

t

 ∈ [

T

]. A feasible solution to the problem is a set of edges

E

t

for each

t

connecting

D

t

to

r

. Instead of obtaining edges for a single day at a time, or for infinitely long (both of which give Steiner tree problems), we

lease

edges for say, {

a day, a week, a month, a year

}. Naturally, leasing an edge for a longer period costs less per unit of time. What is a good leasing strategy? In this paper, we give a general approach to solving a wide class of such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization. All our results are in the offline setting.

Following the well-studied two-stage optimization framework for stochastic optimization [15,8], we study approximation algorithms for robust two-stage optimization problems with an exponential number of scenarios. Prior to this work, Dhamdhere et al. [8] introduced approximation algorithms for two-stage robust optimization problems with explicitly given scenarios. In this paper, we assume the set of possible scenarios is given implicitly, for example by an upper bound on the number of active clients. In two-stage robust optimization, we need to pre-purchase some resources in the first stage before the adversary’s action. In the second stage, after the adversary chooses the clients that need to be covered, we need to complement our solution by purchasing additional resources at an inflated price. The goal is to minimize the cost in the worst-case scenario. We give a general approach for solving such problems using LP rounding. Our approach uncovers an interesting connection between robust optimization and online competitive algorithms. We use this approach, together with known online algorithms, to develop approximation algorithms for several robust covering problems, such as set cover, vertex cover, and edge cover. We also study a simple

buy-at-once

algorithm that either covers all items in the first stage or does nothing in the first stage and waits to build the complete solution in the second stage. We show that this algorithm gives tight approximation factors for unweighted variants of these covering problems, but performs poorly for general weighted problems.

We study the classical

multi-item capacitated lot-sizing problem

with hard capacities. There are

N

items, each of which has specified sequence of demands over a finite planning horizon of discrete

T

periods; the demands are known in advance but can vary from period to period. All demands must be satisfied on time. Each order incurs a time-dependent

fixed ordering cost

regardless of the combination of items or the number of units ordered, but the total number of units ordered cannot exceed a given capacity

C

. On the other hand, carrying inventory from period to period incurs

holding costs

. The goal is to find a feasible solution with minimum overall ordering and holding costs.

We show that the problem is strongly NP-Hard, and then propose a novel facility location type LP relaxation that is based on an exponentially large subset of the well-known

flow-cover inequalities

; the proposed LP can be solved to optimality in polynomial time via an efficient separation procedure for this subset of inequalities. Moreover, the optimal solution of the LP can be rounded to a feasible integer solution with cost that is at most twice the optimal cost; this provides a 2-Approximation algorithm, being the first constant approximation algorithm for the problem. We also describe an interesting

on-the-fly

variant of the algorithm that does not require to solve the LP a-priori with all the flow-cover inequalities. As a by-product we obtain the first theoretical proof regarding the strength of flow-cover inequalities in capacitated inventory models. We believe that some of the novel algorithmic ideas proposed in this paper have a promising potential in constructing strong LP relaxations and LP-based approximation algorithms for other inventory models, and for the capacitated facility location problem.

A cost-sharing problem is defined by a set of players vying to receive some good or service, and a cost function describing the cost incurred by the auctioneer as a function of the set of winners. A cost-sharing mechanism is a protocol that decides which players win the auction and at what prices. Three desirable but provably mutually incompatible properties of a cost-sharing mechanism are: incentive-compatibility, meaning that players are motivated to bid their true private value for receiving the good; budget-balance, meaning that the mechanism recovers its incurred cost with the prices charged; and efficiency, meaning that the cost incurred and the value to the players served are traded off in an optimal way.

Our work is motivated by the following fundamental question: for which cost-sharing problems are incentive-compatible mechanisms with good approximate budget-balance and efficiency possible? We focus on cost functions defined implicitly by NP-hard combinatorial optimization problems, including the metric uncapacitated facility location problem, the Steiner tree problem, and rent-or-buy network design problems. For facility location and rent-or-buy network design, we establish for the first time that approximate budget-balance and efficiency are simultaneously possible. For the Steiner tree problem, where such a guarantee was previously known, we prove a new, optimal lower bound on the approximate efficiency achievable by the wide and natural class of “Moulin mechanisms”. This lower bound exposes a latent approximation hierarchy among different cost-sharing problems.

Given a graph

G

 = (

V

,

E

) with an edge cost and families

$\mathcal{V}_i\subseteq 2^V$

,

i

 = 1,2,...,

m

of disjoint subsets, an edge subset

F

 ⊆ 

E

is called a set connector if, for each

$\mathcal{V}_i$

, the graph

$(V,F)/\mathcal{V}_i$

obtained from (

V

,

F

) by contracting each

$X\in \mathcal{V}_i$

into a single vertex

x

has a property that every two contracted vertices

x

and

x

′ are connected in

$(V,F)/\mathcal{V}_i$

. In this paper, we introduce a problem of finding a minimum cost set connector, which contains several important network design problems such as the Steiner forest problem, the group Steiner tree problem, and the NA-connectivity augmentation problem as its special cases. We derive an approximate integer decomposition property from a fractional packing theorem of set connectors, and present a strongly polynomial 2

α

-approximation algorithm for the set connector problem, where

$\alpha=\max_{1 \leq i \leq m}(\sum_{X \in \mathcal{V}_i}|X|)-1$

.