Search Results

Documents authored by Iglesias, Jennifer

Document
DOI: 10.4230/LIPIcs.ESA.2017.46
Single-Sink Fractionally Subadditive Network Design

Authors: Guru Guruganesh, Jennifer Iglesias, R. Ravi, and Laura Sanita

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We study a generalization of the Steiner tree problem, where we are given a weighted network G together with a collection of k subsets of its vertices and a root r. We wish to construct a minimum cost network such that the network supports one unit of flow to the root from every node in a subset simultaneously. The network constructed does not need to support flows from all the subsets simultaneously. We settle an open question regarding the complexity of this problem for k=2, and give a 3/2-approximation algorithm that improves over a (trivial) known 2-approximation. Furthermore, we prove some structural results that prevent many well-known techniques from doing better than the known O(log n)-approximation. Despite these obstacles, we conjecture that this problem should have an O(1)-approximation. We also give an approximation result for a variant of the problem where the solution is required to be a path.
Cite as

Guru Guruganesh, Jennifer Iglesias, R. Ravi, and Laura Sanita. Single-Sink Fractionally Subadditive Network Design. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{guruganesh_et_al:LIPIcs.ESA.2017.46,
  author =	{Guruganesh, Guru and Iglesias, Jennifer and Ravi, R. and Sanita, Laura},
  title =	{{Single-Sink Fractionally Subadditive Network Design}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.46},
  URN =		{urn:nbn:de:0030-drops-78581},
  doi =		{10.4230/LIPIcs.ESA.2017.46},
  annote =	{Keywords: Network design, single-commodity flow, approximation algorithms, Steiner tree}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.517
Rumors Across Radio, Wireless, Telephone

Authors: Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi, and Ravi Sundaram

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

Abstract
We study the problem of computing a minimum time schedule to spread rumors in a given graph under several models: In the radio model, all neighbors of a transmitting node listen to the messages and are able to record it only when no other neighbor is transmitting; In the wireless model (also called the edge-star model), each transmitter is at a different frequency to which any neighbor can tune to, but only one neighboring transmission can be accessed in this way; In the telephone model, the set of transmitter-receiver pairs form a matching in the graph. The rumor spreading problems assume a message at one or several nodes of the graph that must reach a target node or set of nodes. The transmission proceeds in synchronous rounds under the rules of the corresponding model. The goal is to compute a schedule that completes in the minimum number of rounds. We present a comprehensive study of approximation algorithms for these problems, and show several reductions from the harder to the easier models for special demands. We show a new hardness of approximation of Omega(n^1/2 - epsilon) for the minimum radio gossip time by a connection to maximum induced matchings. We give the first sublinear approximation algorithms for the most general case of the problem under the wireless model; we also consider various special cases such as instances with symmetric demands and give better approximation algorithms. Our work exposes the relationships across the models and opens up several new avenues for further study.
Cite as

Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi, and Ravi Sundaram. Rumors Across Radio, Wireless, Telephone. 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. 517-528, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{iglesias_et_al:LIPIcs.FSTTCS.2015.517,
  author =	{Iglesias, Jennifer and Rajaraman, Rajmohan and Ravi, R. and Sundaram, Ravi},
  title =	{{Rumors Across Radio, Wireless, Telephone}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{517--528},
  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.517},
  URN =		{urn:nbn:de:0030-drops-56383},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.517},
  annote =	{Keywords: Broadcast, Gossip, Approximation algorithms, Graph algorithms, Hardness of Approximation}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.381
Designing Overlapping Networks for Publish-Subscribe Systems

Authors: Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi, and Ravi Sundaram

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
From the publish-subscribe systems of the early days of the Internet to the recent emergence of Web 3.0 and IoT (Internet of Things), new problems arise in the design of networks centered at producers and consumers of constantly evolving information. In a typical problem, each terminal is a source or sink of information and builds a physical network in the form of a tree or an overlay network in the form of a star rooted at itself. Every pair of pub-sub terminals that need to be coordinated (e.g. the source and sink of an important piece of control information) define an edge in a bipartite demand graph; the solution must ensure that the corresponding networks rooted at the endpoints of each demand edge overlap at some node. This simple overlap constraint, and the requirement that each network is a tree or a star, leads to a variety of new questions on the design of overlapping networks. In this paper, for the general demand case of the problem, we show that a natural LP formulation has a non-constant integrality gap; on the positive side, we present a logarithmic approximation for the general demand case. When the demand graph is complete, however, we design approximation algorithms with small constant performance ratios, irrespective of whether the pub networks and sub networks are required to be trees or stars.
Cite as

Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi, and Ravi Sundaram. Designing Overlapping Networks for Publish-Subscribe Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 381-395, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{iglesias_et_al:LIPIcs.APPROX-RANDOM.2015.381,
  author =	{Iglesias, Jennifer and Rajaraman, Rajmohan and Ravi, R. and Sundaram, Ravi},
  title =	{{Designing Overlapping Networks for Publish-Subscribe Systems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{381--395},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.381},
  URN =		{urn:nbn:de:0030-drops-53133},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.381},
  annote =	{Keywords: Approximation Algorithms, Steiner Trees, Publish-Subscribe Systems, Integrality Gap, VPN.}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact