Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

It is well known that the maximum weighted independent set (MWIS) problem is NP-complete. Moreover, optimal scheduling in wireless networks requires solving a MWIS problem. Consequently, it is widely believed that optimal scheduling cannot be solved in practical networks. However, there are many cases where there is a significant difference between worst-case complexity and practical complexity. This paper examines the practical complexity of the MWIS problem through extensive computational experimentation. In all, over 10000 topologies are examined. It is found that the MWIS problem can be solved quickly, for example, for a 2048 node topology, it can be solved in approximately one second. Moreover, it appears that the average computational complexity grows polynomially with the number of nodes and linearly with the mean degree of the conflict graph.

REFERENCES

• 1: L. Tassiulas and A. Ephremides, "Jointly optimal routing and scheduling in packet radio networks", IEEE Trans. on Info. Theory, vol. 38, no. 1, pp. 165--168, Jan 1992.
• 2: E. Arikan, "Some complexity results about packet radio networks", IEEE Trans. on Info. Theory, vol. 30, no. 4, pp. 681--685, Jul 1984.
• 3: L. Bui, A. Eryilmaz, R. Srikant, and X. Wu, "Joint congestion control and distributed schedulingin multihop wireless networks with a node-exclusive interference model", in Infocom, 2006.
• 4: Xiaojun Lin , Ness B. Shroff, The impact of imperfect scheduling on cross-layer congestion control in wireless networks, IEEE/ACM Transactions on Networking (TON), v.14 n.2, p.302-315, April 2006 [doi>10.1109/TENT.2006.872546]
• 5: L. Chen, S. H. Low, M. Chiang, and J. C. Doyle, "Cross-layer congestion control, routing and scheduling design in ad hoc wireless networks", in Infocom, 2006.
• 6: R. M. Karp, "Reducibility among combinatorial problems", in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. Plenum, 1972, pp. 85--103.
• 7: J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
• 8: M. Grotschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Berlin: Springer-Verlag, 1993.
• 9: Tomomi Matsui, Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs, Revised Papers from the Japanese Conference on Discrete and Computational Geometry, p.194-200, December 09-12, 1998
• 10: G. Valiente, A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs. Springer, 2003, vol. 2906, pp. 129--137.
• 11: G. H. Chen , M. T. Kuo , J. P. Sheu, An optimal time algorithm for finding a maximum weight independent set in a tree, BIT, v.28 n.2, p.353-356, February 1988 [doi>10.1007/BF01934098]
• 12: G. Minty, "On maximal independent sets of vertices in claw-free graphs", J. Combinatorial Theory, vol. B, no. 28, pp. 284--304, 1980.
• 13: V. E. Alekseev and V. V. Lozin, "Augmenting graphs for independent sets", Rutgers Center of Operations Research, Tech. Rep. 59-2000, 2000.
• 14: V. Klee and G. J. Minty, "How good is the simplex algorithm", in Inequalities III, O. Shisha, Ed. New York: Academic Press, 1972, pp. 159--175.
• 15: J. Nocedal and S. Wright, Numerical Optimization. Springer, 2000.
• 16: ILOG, "CPLEX", 2008.
• 17: Dash Optimization, "Xpress optimizer", 2007.
• 18: V. Damerow, "Average and smoothed complexity of geometric structures", Ph.D. dissertation, Universitat at Paderborn, 2005.
• 19: B Bollobás , T I Fenner , A M Frieze, An algorithm for finding Hamilton cycles in random graphs, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.430-439, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22193]
• 20: Ljubomir Perkovic , Bruce Reed , Dana Scott, Edge coloring, polyhedra and probability, Carnegie Mellon University, Pittsburgh, PA, 1998
• 21: Herbert S. Wilf, Algorithms and Complexity, A. K. Peters, Ltd., Natick, MA, 2002
• 22: A. Goldberg, "On the complexity of the satisfiability problem", New York University, Tech. Rep. Courant Computer Science Report 16, 1979.
• 23: A. Goldberg, P. W. Purdom, and C. A. Brown, "Average time analysis of simplified davis-putnam procedures", Information Processing Letters, vol. 15, pp. 72--75, 1982.
• 24: J. N. Hooker, "Resolution vs. cutting plane solution of interference problems: Some computational experience", Operations Research Letters, vol. 7, pp. 1--7, 1988.
• 25: A. P. Kamath , Narendra Karmarkar , K. G. Ramakrishnan , Mauricio G. C. Resende, Computational Experience with an Interior Point Algorithm on the Satisfiability Problem, Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, p.333-349, May 28-30, 1990
• 26: D. G. Mitchell, B. Selman, and H. J. Levesque, "Hard and easy distributions for SAT problems", in Proceedings of the Tenth National Conference on Artificial Intelligence, P. Rosenbloom and P. Szolovits, Eds. Menlo Park, California: AAAI Press, 1992, pp. 459--465. {Online}. Available: citeseer.ist.psu.edu/mitchell92hard.html
• 27: S. Bohacek and P. Wang, "Practical computation of optimal schedules in multihop wireless networks", submitted 2007, available at http://udelmodels.eecis.udel.edu.
• 28: Stephan Bohacek , Peng Wang, Communication models for throughput optimization in mesh networks, Proceedings of the 5th ACM symposium on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 27-28, 2008, Vancouver, British Columbia, Canada [doi>10.1145/1454609.1454627]
• 29: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 30: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 31: S. Bohacek, V. Sridhara, and J. Kim, "UDel Models", available at: http://udelmodels.eecis.udel.edu/.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Keywords:
maximum weighted independent set, optimal scheduling, wireless mesh network