×

Hyperbolic set covering problems with competing ground-set elements. (English) Zbl 1254.90119

Summary: Motivated by a challenging problem arising in wireless network design, we investigate a new nonlinear variant of the set covering problem with hyperbolic objective function. Each ground-set element (user) competes with all its neighbors (interfering users) for a shared resource (the network access time), and the goal is to maximize the sum of the resource share assigned to each ground-set element (the network efficiency) while covering all of them. The hyperbolic objective function privileges covers with limited overlaps among selected subsets. In a sense, this variant lies in between the set partitioning problem, where overlaps are forbidden, and the standard set covering problem, where overlaps are not an issue at all. We study the complexity and approximability of generic and Euclidean versions of the problem, present an efficient Lagrangean relaxation approach to tackle medium-to-large-scale instances, and compare the computational results with those obtained by linearizations.

MSC:

90C10 Integer programming
90C27 Combinatorial optimization
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Amaldi, E., Capone, A., Cesana, M., Malucelli, F.: Optimizing WLAN radio coverage. In: Proceedings of the 2004 IEEE International Conference on Communications, vol. 1, pp. 180–184 (2004)
[2] Balas E., Padberg M.W.: Set partitioning: A survey. SIAM Rev. 18(4), 710–760 (1976) · Zbl 0347.90064
[3] Bazaraa, M.S.: A cutting-plane algorithm for the quadratic set-covering problem. Oper. Res. 23(1) (1975) · Zbl 0331.90043
[4] Beasley J.E.: OR-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069–1072 (1990)
[5] Berman, P., DasGupta, B., Sontag, E.D.: Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. In: APPROX: international workshop on approximation algorithms for combinatorial optimization (2004) · Zbl 1106.68432
[6] Bosio, S.: Instance library for the hyperbolic set covering problem. Available online at http://orgroup.dei.polimi.it/people/bosio/Instances.zip
[7] Bosio, S.: On a new class of set covering problems arising in wireless network design. Ph.D. thesis, Dipartimento di Matematica, Politecnico di Milano, April (2006). Available online at http://orgroup.dei.polimi.it/people/bosio/publications/PhD.pdf · Zbl 1151.90499
[8] Bosio S., Capone A., Cesana M.: Radio planning of wireless local area networks. IEEE/ACM Trans. Netw. 15(6), 1414–1427 (2007)
[9] Ceria S., Nobili P., Sassano A.: Set covering problem. In: Dell’Amico, M., Maffioli, F., Martello, S. (eds) Annotated bibliographies in combinatorial optimization, Wiley, New York (1997) · Zbl 1068.90506
[10] Chvátal V.: A greedy heuristic for the set covering problem. Math. Oper. Res. 4, 233–235 (1979) · Zbl 0443.90066
[11] Cornuejols, G.: Combinatorial optimization: packing and covering. Number 74 in CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM (2001)
[12] Engebretsen, L., Holmerin, J.: Clique is hard to approximate within n 1(1). In: Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP 2000), Lecture Notes in Computer Science, July 2000 · Zbl 0973.68079
[13] Escoffier, B., Hammer, P.L.: Approximation of the quadratic set covering problem. Technical report 2005–09, DIMACS (2005)
[14] Feige U.: A threshold of ln(n) for approximating set cover. J. ACM 45, 634–652 (1998) · Zbl 1065.68573
[15] Fowler R.J., Paterson M.S., Tanimoto S.L.: Optimal packing and covering in the plane are NP- complete. Inf. Process. Lett. 12, 133–137 (1981) · Zbl 0469.68053
[16] Frangioni, A.: Object bundle package–an OOP version of a proximal bundle algorithm for linearly constrained nondifferentiable convex optimization. Available online at http://www.di.unipi.it/\(\sim\)frangio (2005)
[17] Garey M.R., Johnson D.S.: Computers and Intractability. A Guide to the Theory of NP- Completeness. W.H. Freeman and Co, New York (1979) · Zbl 0411.68039
[18] Hall N.G., Hochbaum D.S.: A fast approximation algorithm for the multicovering problem. Discrete Appl. Math. 15, 35–40 (1986) · Zbl 0602.90110
[19] Hammer, P.L.: Logical analysis of data: from combinatorial optimization to biomedical, financial and management applications. In: Fifth International Colloquium on Graphs and Optimisation (GO-V), 2006 (personal communication)
[20] Hammer P.L., Rudeanu S.: Boolean Methods in Operations Research and Related Areas. Springer, Dordrecht (1968) · Zbl 0155.28001
[21] Hansen P., Poggi de Aragão M., Ribeiro C.: Boolean query optimization and the 0-1 hyperbolic sum problem. Ann. Math. Artif. Intell. 1, 97–109 (1990) · Zbl 0870.68048
[22] Hansen P., Poggi de Aragão M., Ribeiro C.: Hyperbolic 0-1 programming and query optimization in information retrieval. Math. Program. 52, 255–263 (1991) · Zbl 0737.90044
[23] Håstad J.: Clique is hard to approximate within n 1 . Acta Math. 182, 105–142 (1999) · Zbl 0989.68060
[24] Hills A.: Large-scale wireless LAN design. IEEE Commun. Mag. 39, 98–107 (2001)
[25] Hochbaum D., Maass W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130–136 (1985) · Zbl 0633.68027
[26] Israeli, Y., Ceder,A.: Transit route design using scheduling and multiobjective programming techniques. In: Proceedings of the Sixth International Workshop on Computer-Aided Scheduling of Public Transport, vol. 430 Lecture Notes in Economics and Mathematical Systems, pp. 56–75 (1995) · Zbl 0854.90059
[27] Mc Cormick G.P.: Nonlinear Programming: Theory, Algorithms and Applications. Wiley, New York (1982)
[28] Papadimitriou C.H.: Computational Complexity. Addison-Wesley, Reading (1994) · Zbl 0833.68049
[29] Prokopyev O.A., Huang H., Pardalos P.M.: On complexity of unconstrained hyperbolic 0-1 programming problems. Oper. Res. Lett. 33(3), 312–318 (2005) · Zbl 1140.90469
[30] Schilling D., Jayaraman V., Barkhi R.: A review of covering problems in facility location. Locat. Sci. 1, 25–55 (1993) · Zbl 0923.90108
[31] Schrijver A.: Combinatorial Optimization, Polyhedra and Efficiency. Springer, Berlin (2003) · Zbl 1041.90001
[32] Stancu-Minasian I.M.: Fractional Programming. Kluwer, Dordrecht (1997) · Zbl 0899.90155
[33] Tawarmalani M., Ahmed S., Sahinidis N.V.: Global optimization of 0-1 hyperbolic programs. J. Glob. Optim. 24, 385–416 (2002) · Zbl 1046.90054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.