8 Search Results for "Bhattacharya, Sayan"


Document
Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary

Authors: Sayan Bhattacharya, Thatchaphol Saranurak, and Pattara Sukprasert

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)


Abstract
Designing dynamic algorithms against an adaptive adversary whose performance match the ones assuming an oblivious adversary is a major research program in the field of dynamic graph algorithms. One of the prominent examples whose oblivious-vs-adaptive gap remains maximally large is the fully dynamic spanner problem; there exist algorithms assuming an oblivious adversary with near-optimal size-stretch trade-off using only polylog(n) update time [Baswana, Khurana, and Sarkar TALG'12; Forster and Goranci STOC'19; Bernstein, Forster, and Henzinger SODA'20], while against an adaptive adversary, even when we allow infinite time and only count recourse (i.e. the number of edge changes per update in the maintained spanner), all previous algorithms with stretch at most log⁵(n) require at least Ω(n) amortized recourse [Ausiello, Franciosa, and Italiano ESA'05]. In this paper, we completely close this gap with respect to recourse by showing algorithms against an adaptive adversary with near-optimal size-stretch trade-off and recourse. More precisely, for any k ≥ 1, our algorithm maintains a (2k-1)-spanner of size O(n^{1+1/k}log n) with O(log n) amortized recourse, which is optimal in all parameters up to a O(log n) factor. As a step toward algorithms with small update time (not just recourse), we show another algorithm that maintains a 3-spanner of size Õ(n^{1.5}) with polylog(n) amortized recourse and simultaneously Õ(√n) worst-case update time.

Cite as

Sayan Bhattacharya, Thatchaphol Saranurak, and Pattara Sukprasert. Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ESA.2022.17,
  author =	{Bhattacharya, Sayan and Saranurak, Thatchaphol and Sukprasert, Pattara},
  title =	{{Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{17:1--17:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.17},
  URN =		{urn:nbn:de:0030-drops-169555},
  doi =		{10.4230/LIPIcs.ESA.2022.17},
  annote =	{Keywords: Algorithms, Dynamic Algorithms, Spanners, Recourse}
}
Document
Adversarially Robust Coloring for Graph Streams

Authors: Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
A streaming algorithm is considered to be adversarially robust if it provides correct outputs with high probability even when the stream updates are chosen by an adversary who may observe and react to the past outputs of the algorithm. We grow the burgeoning body of work on such algorithms in a new direction by studying robust algorithms for the problem of maintaining a valid vertex coloring of an n-vertex graph given as a stream of edges. Following standard practice, we focus on graphs with maximum degree at most Δ and aim for colorings using a small number f(Δ) of colors. A recent breakthrough (Assadi, Chen, and Khanna; SODA 2019) shows that in the standard, non-robust, streaming setting, (Δ+1)-colorings can be obtained while using only Õ(n) space. Here, we prove that an adversarially robust algorithm running under a similar space bound must spend almost Ω(Δ²) colors and that robust O(Δ)-coloring requires a linear amount of space, namely Ω(nΔ). We in fact obtain a more general lower bound, trading off the space usage against the number of colors used. From a complexity-theoretic standpoint, these lower bounds provide (i) the first significant separation between adversarially robust algorithms and ordinary randomized algorithms for a natural problem on insertion-only streams and (ii) the first significant separation between randomized and deterministic coloring algorithms for graph streams, since deterministic streaming algorithms are automatically robust. We complement our lower bounds with a suite of positive results, giving adversarially robust coloring algorithms using sublinear space. In particular, we can maintain an O(Δ²)-coloring using Õ(n √Δ) space and an O(Δ³)-coloring using Õ(n) space.

Cite as

Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Adversarially Robust Coloring for Graph Streams. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 37:1-37:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{chakrabarti_et_al:LIPIcs.ITCS.2022.37,
  author =	{Chakrabarti, Amit and Ghosh, Prantar and Stoeckl, Manuel},
  title =	{{Adversarially Robust Coloring for Graph Streams}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{37:1--37:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.37},
  URN =		{urn:nbn:de:0030-drops-156332},
  doi =		{10.4230/LIPIcs.ITCS.2022.37},
  annote =	{Keywords: Data streaming, graph algorithms, graph coloring, lower bounds, online algorithms}
}
Document
Deterministic Dynamic Matching in Worst-Case Update Time

Authors: Peter Kiss

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
We present deterministic algorithms for maintaining a (3/2 + ε) and (2 + ε)-approximate maximum matching in a fully dynamic graph with worst-case update times Ô(√n) and Õ(1) respectively. The fastest known deterministic worst-case update time algorithms for achieving approximation ratio (2 - δ) (for any δ > 0) and (2 + ε) were both shown by Roghani et al. [arXiv'2021] with update times O(n^{3/4}) and O_ε(√n) respectively. We close the gap between worst-case and amortized algorithms for the two approximation ratios as the best deterministic amortized update times for the problem are O_ε(√n) and Õ(1) which were shown in Bernstein and Stein [SODA'2021] and Bhattacharya and Kiss [ICALP'2021] respectively. The algorithm achieving (3/2 + ε) approximation builds on the EDCS concept introduced by the influential paper of Bernstein and Stein [ICALP'2015]. Say that H is a (α, δ)-approximate matching sparsifier if at all times H satisfies that μ(H) ⋅ α + δ ⋅ n ≥ μ(G) (define (α, δ)-approximation similarly for matchings). We show how to maintain a locally damaged version of the EDCS which is a (3/2 + ε, δ)-approximate matching sparsifier. We further show how to reduce the maintenance of an α-approximate maximum matching to the maintenance of an (α, δ)-approximate maximum matching building based on an observation of Assadi et al. [EC'2016]. Our reduction requires an update time blow-up of Ô(1) or Õ(1) and is deterministic or randomized against an adaptive adversary respectively. To achieve (2 + ε)-approximation we improve on the update time guarantee of an algorithm of Bhattacharya and Kiss [ICALP'2021]. In order to achieve both results we explicitly state a method implicitly used in Nanongkai and Saranurak [STOC'2017] and Bernstein et al. [arXiv'2020] which allows to transform dynamic algorithms capable of processing the input in batches to a dynamic algorithms with worst-case update time. Independent Work: Independently and concurrently to our work Grandoni et al. [arXiv'2021] has presented a fully dynamic algorithm for maintaining a (3/2 + ε)-approximate maximum matching with deterministic worst-case update time O_ε(√n).

Cite as

Peter Kiss. Deterministic Dynamic Matching in Worst-Case Update Time. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 94:1-94:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{kiss:LIPIcs.ITCS.2022.94,
  author =	{Kiss, Peter},
  title =	{{Deterministic Dynamic Matching in Worst-Case Update Time}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{94:1--94:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.94},
  URN =		{urn:nbn:de:0030-drops-156909},
  doi =		{10.4230/LIPIcs.ITCS.2022.94},
  annote =	{Keywords: Dynamic Algorithms, Matching, Approximate Matching, EDCS}
}
Document
Beating the Folklore Algorithm for Dynamic Matching

Authors: Mohammad Roghani, Amin Saberi, and David Wajc

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
The maximum matching problem in dynamic graphs subject to edge updates (insertions and deletions) has received much attention over the last few years; a multitude of approximation/time tradeoffs were obtained, improving upon the folklore algorithm, which maintains a maximal (and hence 2-approximate) matching in O(n) worst-case update time in n-node graphs. We present the first deterministic algorithm which outperforms the folklore algorithm in terms of both approximation ratio and worst-case update time. Specifically, we give a (2-Ω(1))-approximate algorithm with O(m^{3/8}) = O(n^{3/4}) worst-case update time in n-node, m-edge graphs. For sufficiently small constant ε > 0, no deterministic (2+ε)-approximate algorithm with worst-case update time O(n^{0.99}) was known. Our second result is the first deterministic (2+ε)-approximate weighted matching algorithm with O_ε(1)⋅ O(∜{m}) = O_ε(1)⋅ O(√n) worst-case update time. Neither of our results were previously known to be achievable by a randomized algorithm against an adaptive adversary. Our main technical contributions are threefold: first, we characterize the tight cases for kernels, which are the well-studied matching sparsifiers underlying much of the (2+ε)-approximate dynamic matching literature. This characterization, together with multiple ideas - old and new - underlies our result for breaking the approximation barrier of 2. Our second technical contribution is the first example of a dynamic matching algorithm whose running time is improved due to improving the recourse of other dynamic matching algorithms. Finally, we show how to use dynamic bipartite matching algorithms as black-box subroutines for dynamic matching in general graphs without incurring the natural 3/2 factor in the approximation ratio which such approaches naturally incur (reminiscent of the integrality gap of the fractional matching polytope in general graphs).

Cite as

Mohammad Roghani, Amin Saberi, and David Wajc. Beating the Folklore Algorithm for Dynamic Matching. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 111:1-111:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{roghani_et_al:LIPIcs.ITCS.2022.111,
  author =	{Roghani, Mohammad and Saberi, Amin and Wajc, David},
  title =	{{Beating the Folklore Algorithm for Dynamic Matching}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{111:1--111:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.111},
  URN =		{urn:nbn:de:0030-drops-157077},
  doi =		{10.4230/LIPIcs.ITCS.2022.111},
  annote =	{Keywords: dynamic matching, dynamic graph algorithms, sublinear algorithms}
}
Document
Track A: Algorithms, Complexity and Games
On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications

Authors: Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
Fair clustering is a variant of constrained clustering where the goal is to partition a set of colored points. The fraction of points of each color in every cluster should be more or less equal to the fraction of points of this color in the dataset. This variant was recently introduced by Chierichetti et al. [NeurIPS 2017] and became widely popular. This paper proposes a new construction of coresets for fair k-means and k-median clustering for Euclidean and general metrics based on random sampling. For the Euclidean space ℝ^d, we provide the first coresets whose size does not depend exponentially on the dimension d. The question of whether such constructions exist was asked by Schmidt, Schwiegelshohn, and Sohler [WAOA 2019] and Huang, Jiang, and Vishnoi [NeurIPS 2019]. For general metric, our construction provides the first coreset for fair k-means and k-median. New coresets appear to be a handy tool for designing better approximation and streaming algorithms for fair and other constrained clustering variants. In particular, we obtain - the first fixed-parameter tractable (FPT) PTAS for fair k-means and k-median clustering in ℝ^d. The near-linear time of our PTAS improves over the previous scheme of Böhm, Fazzone, Leonardi, and Schwiegelshohn [ArXiv 2020] with running time n^{poly(k/ε)}; - FPT "true" constant-approximation for metric fair clustering. All previous algorithms for fair k-means and k-median in general metric are bicriteria and violate the fairness constraints; - FPT 3-approximation for lower-bounded k-median improving the best-known 3.736 factor of Bera, Chakrabarty, and Negahbani [ArXiv 2019]; - the first FPT constant-approximations for metric chromatic clustering and 𝓁-Diversity clustering; - near linear-time (in n) PTAS for capacitated and lower-bounded clustering improving over PTAS of Bhattacharya, Jaiswal, and Kumar [TOCS 2018] with super-quadratic running time; - a streaming (1+ε)-approximation for fair k-means and k-median of space complexity polynomial in k, d, ε and log{n} (the previous algorithms have exponential space complexity on either d or k).

Cite as

Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.ICALP.2021.23,
  author =	{Bandyapadhyay, Sayan and Fomin, Fedor V. and Simonov, Kirill},
  title =	{{On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.23},
  URN =		{urn:nbn:de:0030-drops-140923},
  doi =		{10.4230/LIPIcs.ICALP.2021.23},
  annote =	{Keywords: fair clustering, coresets, approximation algorithms}
}
Document
Track A: Algorithms, Complexity and Games
Deterministic Rounding of Dynamic Fractional Matchings

Authors: Sayan Bhattacharya and Peter Kiss

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
We present a framework for deterministically rounding a dynamic fractional matching. Applying our framework in a black-box manner on top of existing fractional matching algorithms, we derive the following new results: (1) The first deterministic algorithm for maintaining a (2-δ)-approximate maximum matching in a fully dynamic bipartite graph, in arbitrarily small polynomial update time. (2) The first deterministic algorithm for maintaining a (1+δ)-approximate maximum matching in a decremental bipartite graph, in polylogarithmic update time. (3) The first deterministic algorithm for maintaining a (2+δ)-approximate maximum matching in a fully dynamic general graph, in small polylogarithmic (specifically, O(log⁴ n)) update time. These results are respectively obtained by applying our framework on top of the fractional matching algorithms of Bhattacharya et al. [STOC'16], Bernstein et al. [FOCS'20], and Bhattacharya and Kulkarni [SODA'19]. Previously, there were two known general-purpose rounding schemes for dynamic fractional matchings. Both these schemes, by Arar et al. [ICALP'18] and Wajc [STOC'20], were randomized. Our rounding scheme works by maintaining a good matching-sparsifier with bounded arboricity, and then applying the algorithm of Peleg and Solomon [SODA'16] to maintain a near-optimal matching in this low arboricity graph. To the best of our knowledge, this is the first dynamic matching algorithm that works on general graphs by using an algorithm for low-arboricity graphs as a black-box subroutine. This feature of our rounding scheme might be of independent interest.

Cite as

Sayan Bhattacharya and Peter Kiss. Deterministic Rounding of Dynamic Fractional Matchings. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ICALP.2021.27,
  author =	{Bhattacharya, Sayan and Kiss, Peter},
  title =	{{Deterministic Rounding of Dynamic Fractional Matchings}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.27},
  URN =		{urn:nbn:de:0030-drops-140960},
  doi =		{10.4230/LIPIcs.ICALP.2021.27},
  annote =	{Keywords: Matching, Dynamic Algorithms, Data Structures}
}
Document
Improved Algorithm for Dynamic b-Matching

Authors: Sayan Bhattacharya, Manoj Gupta, and Divyarthi Mohan

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


Abstract
Recently there has been extensive work on maintaining (approximate) maximum matchings in dynamic graphs. We consider a generalisation of this problem known as the maximum b-matching: Every node v has a positive integral capacity b_v, and the goal is to maintain an (approximate) maximum-cardinality subset of edges that contains at most b_v edges incident on every node v. The maximum matching problem is a special case of this problem where b_v = 1 for every node v. Bhattacharya, Henzinger and Italiano [ICALP 2015] showed how to maintain a O(1) approximate maximum b-matching in a graph in O(log^3 n) amortised update time. Their approximation ratio was a large (double digit) constant. We significantly improve their result both in terms of approximation ratio as well as update time. Specifically, we design a randomised dynamic algorithm that maintains a (2+epsilon)-approximate maximum $b$-matching in expected amortised O(1/epsilon^4) update time. Thus, for every constant epsilon in (0, 1), we get expected amortised O(1) update time. Our algorithm generalises the framework of Baswana, Gupta, Sen [FOCS 2011] and Solomon [FOCS 2016] for maintaining a maximal matching in a dynamic graph.

Cite as

Sayan Bhattacharya, Manoj Gupta, and Divyarthi Mohan. Improved Algorithm for Dynamic b-Matching. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ESA.2017.15,
  author =	{Bhattacharya, Sayan and Gupta, Manoj and Mohan, Divyarthi},
  title =	{{Improved Algorithm for Dynamic b-Matching}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{15:1--15: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.15},
  URN =		{urn:nbn:de:0030-drops-78443},
  doi =		{10.4230/LIPIcs.ESA.2017.15},
  annote =	{Keywords: dynamic data structures, graph algorithms}
}
Document
Welfare Maximization with Friends-of-Friends Network Externalities

Authors: Sayan Bhattacharya, Wolfgang Dvorák, Monika Henzinger, and Martin Starnberger

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
Online social networks allow the collection of large amounts of data about the influence between users connected by a friendship-like relationship. When distributing items among agents forming a social network, this information allows us to exploit network externalities that each agent receives from his neighbors that get the same item. In this paper we consider Friends-of-Friends (2-hop) network externalities, i.e., externalities that not only depend on the neighbors that get the same item but also on neighbors of neighbors. For these externalities we study a setting where multiple different items are assigned to unit-demand agents. Specifically, we study the problem of welfare maximization under different types of externality functions. Let n be the number of agents and m be the number of items. Our contributions are the following: (1) We show that welfare maximization is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop) externalities it is NP-hard to approximate social welfare better than (1-1/e). (2) On the positive side we present (i) an O(sqrt n)-approximation algorithm for general concave externality functions, (ii) an O(\log m)-approximation algorithm for linear externality functions, and (iii) an (1-1/e)\frac{1}{6}-approximation algorithm for 2-hop step function externalities. We also improve the result from [6] for 1-hop step function externalities by giving a (1-1/e)/2-approximation algorithm.

Cite as

Sayan Bhattacharya, Wolfgang Dvorák, Monika Henzinger, and Martin Starnberger. Welfare Maximization with Friends-of-Friends Network Externalities. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 90-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.STACS.2015.90,
  author =	{Bhattacharya, Sayan and Dvor\'{a}k, Wolfgang and Henzinger, Monika and Starnberger, Martin},
  title =	{{Welfare Maximization with Friends-of-Friends Network Externalities}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{90--102},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.90},
  URN =		{urn:nbn:de:0030-drops-49066},
  doi =		{10.4230/LIPIcs.STACS.2015.90},
  annote =	{Keywords: network externalities, welfare maximization, approximation algorithms}
}
  • Refine by Author
  • 4 Bhattacharya, Sayan
  • 2 Kiss, Peter
  • 1 Bandyapadhyay, Sayan
  • 1 Chakrabarti, Amit
  • 1 Dvorák, Wolfgang
  • Show More...

  • Refine by Classification
  • 1 Theory of computation
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → Sparsification and spanners
  • Show More...

  • Refine by Keyword
  • 3 Dynamic Algorithms
  • 2 Matching
  • 2 approximation algorithms
  • 2 graph algorithms
  • 1 Algorithms
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 4 2022
  • 2 2021
  • 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