Wireless Ad Hoc and Sensor Networks

Approximation Algorithms for Load-balanced Virtual Backbone

 73

as an integer nonlinear programming INP

MDMIS

as follows:

min z = max{d

i

|∀v

i

∈ D}

s.t. x

i

+



v

j

∈N

1

(v

i

)

x

j

≥ 1;



v

j

∈N

1

(v

i

)

x

i

·x

j

= 0;

x

i

,x

j

∈{0, 1}, ∀v

i

,v

j

∈ V.

(INP

MDMIS

)

Since the IS property constraint is quadratic, the formulated integer programming

INP

MDMIS

is not linear. To linearize INP

MDMIS

, the quadratic constraint is eliminated

by applying the techniques proposed in [70]. More specifically, the product x

i

·x

j

is

replaced by a new binary variable

χ

ij

, on which several additional constraints are

imposed. As a consequence, we can reformulate INP

MDMIS

exactly to an integer

linear programming ILP

MDMIS