8 Search Results for "Gil, Yuval"

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.16
Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs

Authors: Yuval Gil

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
We design new deterministic CONGEST approximation algorithms for maximum weight independent set (MWIS) in sparse graphs. As our main results, we obtain new Δ(1+ε)-approximation algorithms as well as algorithms whose approximation ratio depend strictly on α, in graphs with maximum degree Δ and arboricity α. For (deterministic) Δ(1+ε)-approximation, the current state-of-the-art is due to a recent breakthrough by Faour et al. [SODA 2023] that showed an O(log² (Δ W)⋅ log (1/ε)+log ^{*}n)-round algorithm, where W is the largest node-weight (this bound translates to O(log² n⋅log (1/ε)) under the common assumption that W = poly(n)). As for α-dependent approximations, a deterministic CONGEST (8(1+ε)⋅α)-approximation algorithm with runtime O(log³ n⋅log (1/ε)) can be derived by combining the aforementioned algorithm of Faour et al. with a method presented by Kawarabayashi et al. [DISC 2020]. As our main results, we show the following. - A deterministic CONGEST algorithm that computes an α^{1+τ}-approximation for MWIS in O(log nlog α) rounds for any constant τ > 0. To the best of our knowledge, this is the fastest runtime of any deterministic non-trivial approximation algorithm for MWIS to date. Furthermore, for the large class of graphs where α = Δ^{1-Θ(1)}, it implies a deterministic Δ^{1-Θ(1)}-approximation algorithm with a runtime of O(log nlog α) which improves upon the result of Faour et al. in both approximation ratio (by a Δ^{Θ(1)} factor) and runtime (by an O(log n/log α) factor). - A deterministic CONGEST algorithm that computes an O(α)-approximation for MWIS in O(α^{τ}log n) rounds for any (desirably small) constant τ > 0. This improves the runtime of the best known deterministic O(α)-approximation algorithm in the case that α = O(polylog n). This also leads to a deterministic Δ(1+ε)-approximation algorithm with a runtime of O(α^{τ}log nlog (1/ε)) which improves upon the runtime of Faour et al. in the case that α = O(polylog n). - A deterministic CONGEST algorithm that computes a (⌊(2+ε)α⌋)-approximation for MWIS in O(αlog n) rounds. This improves upon the best known α-dependent approximation ratio by a constant factor. - A deterministic CONGEST algorithm that computes a 2d²-approximation for MWIS in time O(d²+log ^{*}n) in a directed graph with out-degree at most d. The dependency on n is (asymptotically) optimal due to a lower bound by Czygrinow et al. [DISC 2008] and Lenzen and Wattenhofer [DISC 2008]. We note that a key ingredient to all of our algorithms is a novel deterministic method that computes a high-weight subset of nodes whose induced subgraph is sparse.
Cite as

Yuval Gil. Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gil:LIPIcs.OPODIS.2023.16,
  author =	{Gil, Yuval},
  title =	{{Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.16},
  URN =		{urn:nbn:de:0030-drops-195067},
  doi =		{10.4230/LIPIcs.OPODIS.2023.16},
  annote =	{Keywords: Approximation algorithms, Sparse graphs, The CONGEST model}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.44
Online Algorithms with Randomly Infused Advice

Authors: Yuval Emek, Yuval Gil, Maciej Pacut, and Stefan Schmid

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We introduce a novel method for the rigorous quantitative evaluation of online algorithms that relaxes the "radical worst-case" perspective of classic competitive analysis. In contrast to prior work, our method, referred to as randomly infused advice (RIA), does not make any assumptions about the input sequence and does not rely on the development of designated online algorithms. Rather, it can be applied to existing online randomized algorithms, introducing a means to evaluate their performance in scenarios that lie outside the radical worst-case regime. More concretely, an online algorithm ALG with RIA benefits from pieces of advice generated by an omniscient but not entirely reliable oracle. The crux of the new method is that the advice is provided to ALG by writing it into the buffer ℬ from which ALG normally reads its random bits, hence allowing us to augment it through a very simple and non-intrusive interface. The (un)reliability of the oracle is captured via a parameter 0 ≤ α ≤ 1 that determines the probability (per round) that the advice is successfully infused by the oracle; if the advice is not infused, which occurs with probability 1 - α, then the buffer ℬ contains fresh random bits (as in the classic online setting). The applicability of the new RIA method is demonstrated by applying it to three extensively studied online problems: paging, uniform metrical task systems, and online set cover. For these problems, we establish new upper bounds on the competitive ratio of classic online algorithms that improve as the infusion parameter α increases. These are complemented with (often tight) lower bounds on the competitive ratio of online algorithms with RIA for the three problems.
Cite as

Yuval Emek, Yuval Gil, Maciej Pacut, and Stefan Schmid. Online Algorithms with Randomly Infused Advice. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.ESA.2023.44,
  author =	{Emek, Yuval and Gil, Yuval and Pacut, Maciej and Schmid, Stefan},
  title =	{{Online Algorithms with Randomly Infused Advice}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.44},
  URN =		{urn:nbn:de:0030-drops-186970},
  doi =		{10.4230/LIPIcs.ESA.2023.44},
  annote =	{Keywords: Online algorithms, competitive analysis, advice}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.27
Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach

Authors: Yuval Emek, Yuval Gil, and Noga Harlev

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Self-stabilization is an important concept in the realm of fault-tolerant distributed computing. In this paper, we propose a new approach that relies on the properties of linear programming duality to obtain self-stabilizing approximation algorithms for distributed graph optimization problems. The power of this new approach is demonstrated by the following results: - A self-stabilizing 2(1+ε)-approximation algorithm for minimum weight vertex cover that converges in O(logΔ /(εlog log Δ)) synchronous rounds. - A self-stabilizing Δ-approximation algorithm for maximum weight independent set that converges in O(Δ+log^* n) synchronous rounds. - A self-stabilizing ((2ρ+1)(1+ε))-approximation algorithm for minimum weight dominating set in ρ-arboricity graphs that converges in O((logΔ)/ε) synchronous rounds. In all of the above, Δ denotes the maximum degree. Our technique improves upon previous results in terms of time complexity while incurring only an additive O(log n) overhead to the message size. In addition, to the best of our knowledge, we provide the first self-stabilizing algorithms for the weighted versions of minimum vertex cover and maximum independent set.
Cite as

Yuval Emek, Yuval Gil, and Noga Harlev. Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.OPODIS.2022.27,
  author =	{Emek, Yuval and Gil, Yuval and Harlev, Noga},
  title =	{{Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.27},
  URN =		{urn:nbn:de:0030-drops-176474},
  doi =		{10.4230/LIPIcs.OPODIS.2022.27},
  annote =	{Keywords: self-stabilization, approximation algorithms, primal-dual}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.20
Locally Restricted Proof Labeling Schemes

Authors: Yuval Emek, Yuval Gil, and Shay Kutten

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Introduced by Korman, Kutten, and Peleg (PODC 2005), a proof labeling scheme (PLS) is a distributed verification system dedicated to evaluating if a given configured graph satisfies a certain property. It involves a centralized prover, whose role is to provide proof that a given configured graph is a yes-instance by means of assigning labels to the nodes, and a distributed verifier, whose role is to verify the validity of the given proof via local access to the assigned labels. In this paper, we introduce the notion of a locally restricted PLS in which the prover’s power is restricted to that of a LOCAL algorithm with a polylogarithmic number of rounds. To circumvent inherent impossibilities of PLSs in the locally restricted setting, we turn to models that relax the correctness requirements by allowing the verifier to accept some no-instances as long as they are not "too far" from satisfying the property in question. To this end, we evaluate (1) distributed graph optimization problems (OptDGPs) based on the notion of an approximate proof labeling scheme (APLS) (analogous to the type of relaxation used in sequential approximation algorithms); and (2) configured graph families (CGFs) based on the notion of a testing proof labeling schemes (TPLS) (analogous to the type of relaxation used in property testing algorithms). The main contribution of the paper comes in the form of two generic compilers, one for OptDGPs and one for CGFs: given a black-box access to an APLS (resp., PLS) for a large class of OptDGPs (resp., CGFs), the compiler produces a locally restricted APLS (resp., TPLS) for the same problem, while losing at most a (1 + ε) factor in the scheme’s relaxation guarantee. An appealing feature of the two compilers is that they only require a logarithmic additive label size overhead.
Cite as

Yuval Emek, Yuval Gil, and Shay Kutten. Locally Restricted Proof Labeling Schemes. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.DISC.2022.20,
  author =	{Emek, Yuval and Gil, Yuval and Kutten, Shay},
  title =	{{Locally Restricted Proof Labeling Schemes}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{20:1--20:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.20},
  URN =		{urn:nbn:de:0030-drops-172111},
  doi =		{10.4230/LIPIcs.DISC.2022.20},
  annote =	{Keywords: proof labeling schemes, generic compilers, SLOCAL algorithms}
}
Document
DOI: 10.4230/LIPIcs.FORC.2021.1
Privately Answering Counting Queries with Generalized Gaussian Mechanisms

Authors: Arun Ganesh and Jiazheng Zhao

Published in: LIPIcs, Volume 192, 2nd Symposium on Foundations of Responsible Computing (FORC 2021)

Abstract
We give the first closed-form privacy guarantees for the Generalized Gaussian mechanism (the mechanism that adds noise x to a vector with probability proportional to exp(-(||x||_p/σ)^p) for some σ, p), in the setting of answering k counting (i.e. sensitivity-1) queries about a database with (ε, δ)-differential privacy (in particular, with low 𝓁_∞-error). Just using Generalized Gaussian noise, we obtain a mechanism such that if the true answers to the queries are the vector d, the mechanism outputs answers d̃ with the 𝓁_∞-error guarantee: 𝔼[||d̃ - d||_∞] = O(√{k log log k log(1/δ)}/ε). This matches the error bound of [Steinke and Ullman, 2017], but using a much simpler mechanism. By composing this mechanism with the sparse vector mechanism (generalizing a technique of [Steinke and Ullman, 2017]), we obtain a mechanism improving the √{k log log k} dependence on k to √{k log log log k}, Our main technical contribution is showing that certain powers of Generalized Gaussians, which follow a Generalized Gamma distribution, are sub-gamma. In subsequent work, the optimal 𝓁_∞-error bound of O(√{k log (1/δ)}/ε) has been achieved by [Yuval Dagan and Gil Kur, 2020] and [Badih Ghazi et al., 2020] independently. However, the Generalized Gaussian mechanism has some qualitative advantages over the mechanisms used in these papers which may make it of interest to both practitioners and theoreticians, both in the setting of answering counting queries and more generally.
Cite as

Arun Ganesh and Jiazheng Zhao. Privately Answering Counting Queries with Generalized Gaussian Mechanisms. In 2nd Symposium on Foundations of Responsible Computing (FORC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 192, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.FORC.2021.1,
  author =	{Ganesh, Arun and Zhao, Jiazheng},
  title =	{{Privately Answering Counting Queries with Generalized Gaussian Mechanisms}},
  booktitle =	{2nd Symposium on Foundations of Responsible Computing (FORC 2021)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-187-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{192},
  editor =	{Ligett, Katrina and Gupta, Swati},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2021.1},
  URN =		{urn:nbn:de:0030-drops-138698},
  doi =		{10.4230/LIPIcs.FORC.2021.1},
  annote =	{Keywords: Differential privacy, counting queries, Generalized Gaussians}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.20
Twenty-Two New Approximate Proof Labeling Schemes

Authors: Yuval Emek and Yuval Gil

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Introduced by Korman, Kutten, and Peleg (Distributed Computing 2005), a proof labeling scheme (PLS) is a system dedicated to verifying that a given configuration graph satisfies a certain property. It is composed of a centralized prover, whose role is to generate a proof for yes-instances in the form of an assignment of labels to the nodes, and a distributed verifier, whose role is to verify the validity of the proof by local means and accept it if and only if the property is satisfied. To overcome lower bounds on the label size of PLSs for certain graph properties, Censor-Hillel, Paz, and Perry (SIROCCO 2017) introduced the notion of an approximate proof labeling scheme (APLS) that allows the verifier to accept also some no-instances as long as they are not "too far" from satisfying the property. The goal of the current paper is to advance our understanding of the power and limitations of APLSs. To this end, we formulate the notion of APLSs in terms of distributed graph optimization problems (OptDGPs) and develop two generic methods for the design of APLSs. These methods are then applied to various classic OptDGPs, obtaining twenty-two new APLSs. An appealing characteristic of our APLSs is that they are all sequentially efficient in the sense that both the prover and the verifier are required to run in (sequential) polynomial time. On the negative side, we establish "combinatorial" lower bounds on the label size for some of the aforementioned OptDGPs that demonstrate the optimality of our corresponding APLSs. For other OptDGPs, we establish conditional lower bounds that exploit the sequential efficiency of the verifier alone (under the assumption that NP ≠ co-NP) or that of both the verifier and the prover (under the assumption that P ≠ NP, with and without the unique games conjecture).
Cite as

Yuval Emek and Yuval Gil. Twenty-Two New Approximate Proof Labeling Schemes. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.DISC.2020.20,
  author =	{Emek, Yuval and Gil, Yuval},
  title =	{{Twenty-Two New Approximate Proof Labeling Schemes}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.20},
  URN =		{urn:nbn:de:0030-drops-130983},
  doi =		{10.4230/LIPIcs.DISC.2020.20},
  annote =	{Keywords: proof labeling schemes, distributed graph problems, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.51
On Weak epsilon-Nets and the Radon Number

Authors: Shay Moran and Amir Yehudayoff

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We show that the Radon number characterizes the existence of weak nets in separable convexity spaces (an abstraction of the Euclidean notion of convexity). The construction of weak nets when the Radon number is finite is based on Helly’s property and on metric properties of VC classes. The lower bound on the size of weak nets when the Radon number is large relies on the chromatic number of the Kneser graph. As an application, we prove an amplification result for weak epsilon-nets.
Cite as

Shay Moran and Amir Yehudayoff. On Weak epsilon-Nets and the Radon Number. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{moran_et_al:LIPIcs.SoCG.2019.51,
  author =	{Moran, Shay and Yehudayoff, Amir},
  title =	{{On Weak epsilon-Nets and the Radon Number}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.51},
  URN =		{urn:nbn:de:0030-drops-104551},
  doi =		{10.4230/LIPIcs.SoCG.2019.51},
  annote =	{Keywords: abstract convexity, weak epsilon nets, Radon number, VC dimension, Haussler packing lemma, Kneser graphs}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.54
A Fast Distributed Stateless Algorithm for alpha-Fair Packing Problems

Authors: Jelena Marasevic, Clifford Stein, and Gil Zussman

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We study weighted alpha-fair packing problems, that is, the problems of maximizing the objective functions (i) sum_j w_j*x_j^{1-alpha}/(1-alpha) when alpha > 0, alpha != 1 and (ii) sum_j w_j*ln(x_j) when alpha = 1, over linear constraints A*x <=b, x >= 0, where wj are positive weights and A and b are non-negative. We consider the distributed computation model that was used for packing linear programs and network utility maximization problems. Under this model, we provide a distributed algorithm for general alpha that converges to an epsilon-approximate solution in time (number of distributed iterations) that has an inverse polynomial dependence on the approximation parameter epsilon and poly-logarithmic dependence on the problem size. This is the first distributed algorithm for weighted alpha-fair packing with poly-logarithmic convergence in the input size. The algorithm uses simple local update rules and is stateless (namely, it allows asynchronous updates, is self-stabilizing, and allows incremental and local adjustments). We also obtain a number of structural results that characterize alpha-fair allocations as the value of alpha is varied. These results deepen our understanding of fairness guarantees in alpha-fair packing allocations, and also provide insight into the behavior of alpha-fair allocations in the asymptotic cases alpha -> 0, alpha -> 1, and alpha -> infinity.
Cite as

Jelena Marasevic, Clifford Stein, and Gil Zussman. A Fast Distributed Stateless Algorithm for alpha-Fair Packing Problems. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{marasevic_et_al:LIPIcs.ICALP.2016.54,
  author =	{Marasevic, Jelena and Stein, Clifford and Zussman, Gil},
  title =	{{A Fast Distributed Stateless Algorithm for alpha-Fair Packing Problems}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{54:1--54:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.54},
  URN =		{urn:nbn:de:0030-drops-63344},
  doi =		{10.4230/LIPIcs.ICALP.2016.54},
  annote =	{Keywords: Fairness, distributed and stateless algorithms, resource allocation}
}
  • Refine by Author
  • 5 Gil, Yuval
  • 4 Emek, Yuval
  • 1 Ganesh, Arun
  • 1 Harlev, Noga
  • 1 Kutten, Shay
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Approximation algorithms analysis
  • 4 Theory of computation → Distributed algorithms
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Security and privacy → Privacy-preserving protocols
  • 1 Theory of computation → Computational geometry
  • Show More...

  • Refine by Keyword
  • 2 approximation algorithms
  • 2 proof labeling schemes
  • 1 Approximation algorithms
  • 1 Differential privacy
  • 1 Fairness
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 2023
  • 1 2016
  • 1 2019
  • 1 2020
  • 1 2021
  • Show More...

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 Imprint Privacy Contact