[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Coordinating Concurrent Transmissions: A Constant-Factor Approximation of Maximum-Weight Independent Set in Local Conflict Graphs

  • Conference paper
Ad-Hoc, Mobile, and Wireless Networks (ADHOC-NOW 2007)

Part of the book series: Lecture Notes in Computer Science ((LNCCN,volume 4686))

Included in the following conference series:

  • 426 Accesses

Abstract

We study the algorithmic problem of coordinating transmissions in a wireless network where radio interference constrains concurrent transmissions on wireless links. We focus on pairwise conflicts between the links; these can be described as a conflict graph. Associated with the conflict graph are two fundamental network coordination tasks: (a) finding a nonconflicting set of links with the maximum total weight, and (b) finding a link schedule with the minimum total length. Our work shows that two assumptions on the geometric structure of conflict graphs suffice to achieve polynomial-time constant-factor approximations: (i) bounded density of devices, and (ii) bounded range of interference. We also show that these assumptions are not sufficient to obtain a polynomial-time approximation scheme for either coordination task.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Jain, K., Padhye, J., Padmanabhan, V.N., Qiu, L.: Impact of interference on multi-hop wireless network performance. Wireless Networks 11(4), 471–487 (2005)

    Article  Google Scholar 

  2. Jansen, K.: Approximate strong separation with application in fractional graph coloring and preemptive scheduling. Theoretical Computer Science 302(1–3), 239–256 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  3. Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: Proc. 42nd Annual Symposium on Foundations of Computer Science FOCS, Las Vegas, NV, USA, October 2001, pp. 538–546. IEEE Computer Society Press, Los Alamitos (2001)

    Google Scholar 

  4. Håstad, J.: Clique is hard to approximate within n 1 − ε. Acta Mathematica 182, 105–142 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  5. Khot, S.: Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring. In: Proc. 42nd Annual Symposium on Foundations of Computer Science FOCS, Las Vegas, NV, USA, October 2001, pp. 600–609. IEEE Computer Society Press, Los Alamitos (2001)

    Google Scholar 

  6. Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. Journal of the ACM 41(5), 960–981 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  7. Goldsmith, A.: Wireless Communications. Cambridge University Press, Cambridge, UK (2005)

    Google Scholar 

  8. Krishnamachari, B.: Networking Wireless Sensors. Cambridge University Press, Cambridge, UK (2005)

    Google Scholar 

  9. Suomela, J.: Approximability of identifying codes and locating-dominating codes. Information Processing Letters 103(1), 28–33 (2007)

    Article  MathSciNet  Google Scholar 

  10. Doyle, P.G., Snell, J.L.: Random Walks and Electric Networks. The Mathematical Association of America, Washington, DC, USA (1984)

    Google Scholar 

  11. Halldórsson, M.M.: Approximations of independent sets in graphs. In: Jansen, K., Rolim, J.D.P. (eds.) APPROX 1998. LNCS, vol. 1444, pp. 1–13. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  12. Halldórsson, M.M.: Approximations of weighted independent set and hereditary subset problems. Journal of Graph Algorithms and Applications 4(1), 1–16 (2000)

    MathSciNet  Google Scholar 

  13. Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing 34(6), 1302–1323 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM 32(1), 130–136 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  15. Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms 26(2), 238–274 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  16. Khanna, S., Motwani, R., Sudan, M., Vazirani, U.: On syntactic versus computational views of approximability. SIAM Journal on Computing 28(1), 164–191 (1999)

    Article  MathSciNet  Google Scholar 

  17. Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences 43(3), 425–440 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  18. Chvátal, V., Ebenegger, C.: A note on line digraphs and the directed max-cut problem. Discrete Applied Mathematics 29(2–3), 165–170 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  19. Erlebach, T., Jansen, K.: Conversion of coloring algorithms into maximum weight independent set algorithms. Discrete Applied Mathematics 148(1), 107–125 (2005)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Helsinki Institute for Information Technology HIIT, Department of Computer Science, University of Helsinki, P.O. Box 68, FI-00014 University of Helsinki, Finland

    Petteri Kaski & Jukka Suomela

  2. Networking Laboratory, Helsinki University of Technology, P.O. Box 3000, FI-02015 TKK, Finland

    Aleksi Penttinen

Authors
  1. Petteri Kaski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Aleksi Penttinen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jukka Suomela
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Evangelos Kranakis Jaroslav Opatrny

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kaski, P., Penttinen, A., Suomela, J. (2007). Coordinating Concurrent Transmissions: A Constant-Factor Approximation of Maximum-Weight Independent Set in Local Conflict Graphs . In: Kranakis, E., Opatrny, J. (eds) Ad-Hoc, Mobile, and Wireless Networks. ADHOC-NOW 2007. Lecture Notes in Computer Science, vol 4686. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74823-6_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-74823-6_6

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-74822-9

  • Online ISBN: 978-3-540-74823-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation