2 Search Results for "Goussevskaia, Olga"


Document
Brief Announcement
Brief Announcement: Distributed SplayNets

Authors: Bruna S. Peres, Olga Goussevskaia, Stefan Schmid, and Chen Avin

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)


Abstract
SplayNets are reconfigurable networks which adjust to the communication pattern over time. We present DiSplayNets, a distributed (concurrent and decentralized) implementation of SplayNets.

Cite as

Bruna S. Peres, Olga Goussevskaia, Stefan Schmid, and Chen Avin. Brief Announcement: Distributed SplayNets. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 58:1-58:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{peres_et_al:LIPIcs.DISC.2017.58,
  author =	{Peres, Bruna S. and Goussevskaia, Olga and Schmid, Stefan and Avin, Chen},
  title =	{{Brief Announcement: Distributed SplayNets}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{58:1--58:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.58},
  URN =		{urn:nbn:de:0030-drops-79661},
  doi =		{10.4230/LIPIcs.DISC.2017.58},
  annote =	{Keywords: Decentralization, Concurrency, Reconfigurable Networks}
}
Document
The Price of Local Power Control in Wireless Scheduling

Authors: Magnús M. Halldórsson and Tigran Tonoyan

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)


Abstract
We consider the problem of scheduling wireless links in the physical model, where we seek an assignment of power levels and a partition of the given set of links into the minimum number of subsets satisfying the signal-to-interference-and-noise-ratio (SINR) constraints. Specifically, we are interested in the efficiency of local power assignment schemes, or oblivious power schemes, in approximating wireless scheduling. Oblivious power schemes are motivated by networking scenarios when power levels must be decided in advance, and not as part of the scheduling computation. We present the first O(log log Delta)-approximation algorithm, which is known to be best possible (in terms of Delta) for oblivious power schemes, where Delta is the longest to shortest link length ratio. We achieve this by representing interference by a conflict graph, which allows the application of graph-theoretic results for a variety of related problems, including the weighted capacity problem. We explore further the contours of approximability and find the choice of power assignment matters; that not all metric spaces are equal; and that the presence of weak links makes the problem harder. Combined, our results resolve the price of local power for wireless scheduling, or the value of allowing unfettered power control.

Cite as

Magnús M. Halldórsson and Tigran Tonoyan. The Price of Local Power Control in Wireless Scheduling. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 529-542, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.FSTTCS.2015.529,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Tonoyan, Tigran},
  title =	{{The Price of Local Power Control in Wireless Scheduling}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{529--542},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.529},
  URN =		{urn:nbn:de:0030-drops-56243},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.529},
  annote =	{Keywords: Wireless Scheduling, Physical Model, Oblivious Power}
}
  • Refine by Author
  • 1 Avin, Chen
  • 1 Goussevskaia, Olga
  • 1 Halldórsson, Magnús M.
  • 1 Peres, Bruna S.
  • 1 Schmid, Stefan
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Concurrency
  • 1 Decentralization
  • 1 Oblivious Power
  • 1 Physical Model
  • 1 Reconfigurable Networks
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail