Search Results

Documents authored by Krysta, Piotr

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.41
What Is the Minimum Number of Random Bits Required for Computability and Efficiency in Anonymous Networks?

Authors: Dariusz R. Kowalski, Piotr Krysta, and Shay Kutten

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

Abstract
Angluin (STOC'80) and Yamashita and Kameda (PODC'88) show that some useful distributed tasks are impossible (for deterministic algorithms) in a general network if nodes do not possess unique identifiers. However, any task decidable in the non-distributed context, can be solved deterministically if the network has a unique leader. Alternatively, much research has been devoted to randomized distributed algorithms in anonymous networks. We present tight upper and lower bounds for the fundamental question: How much randomness is necessary and sufficient to solve Leader Election (LE) in anonymous networks, i.e., to transform an anonymous network into a non-anonymous one? We prove that at least one random bit per node is required in some cases. Surprisingly, a single random bit is also enough, for a total of n bits, where n is the number of nodes. However, the time complexity of our (total of) n random bits algorithm for general networks turned out to be impractically high. Hence, we also developed time-efficient algorithms for the very symmetric graphs of cliques and cycles, paying only an additional cost of o(n) random bits. The primary steps of our algorithms are of independent interest. At first glance, it seems that using one random bit per node, any algorithm can distinguish only two sets of nodes: those with 0 and those with 1. Our algorithms manage to partition the nodes into more than two sets with high probability. In some sense, they perform the task of a "distributed pseudorandom generator", for example, one of our algorithms turns n bits, one per node, into n unique (with high probability) numbers. Even though a complete graph looks very symmetric, the algorithms explore interesting asymmetries inherent in any n permutations (of n values each), if each describes the assignment (by the adversary) of ports in a node to edges leading to neighbors. Finally, we show how to transform any randomized algorithm that generates xn+o(n) random bits in total to one where each node generates at most x+1 bits. Our results apply to both synchronous and asynchronous networks.
Cite as

Dariusz R. Kowalski, Piotr Krysta, and Shay Kutten. What Is the Minimum Number of Random Bits Required for Computability and Efficiency in Anonymous Networks?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 41:1-41:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kowalski_et_al:LIPIcs.APPROX/RANDOM.2025.41,
  author =	{Kowalski, Dariusz R. and Krysta, Piotr and Kutten, Shay},
  title =	{{What Is the Minimum Number of Random Bits Required for Computability and Efficiency in Anonymous Networks?}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{41:1--41:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.41},
  URN =		{urn:nbn:de:0030-drops-244071},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.41},
  annote =	{Keywords: Distributed computability, Anonymous Networks, Randomness, Leader Election}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.141
House Markets with Matroid and Knapsack Constraints

Authors: Piotr Krysta and Jinshan Zhang

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

Abstract
Classical online bipartite matching problem and its generalizations are central algorithmic optimization problems. The second related line of research is in the area of algorithmic mechanism design, referring to the broad class of house allocation or assignment problems. We introduce a single framework that unifies and generalizes these two streams of models. Our generalizations allow for arbitrary matroid constraints or knapsack constraints at every object in the allocation problem. We design and analyze approximation algorithms and truthful mechanisms for this framework. Our algorithms have best possible approximation guarantees for most of the special instantiations of this framework, and are strong generalizations of the previous known results.
Cite as

Piotr Krysta and Jinshan Zhang. House Markets with Matroid and Knapsack Constraints. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 141:1-141:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{krysta_et_al:LIPIcs.ICALP.2016.141,
  author =	{Krysta, Piotr and Zhang, Jinshan},
  title =	{{House Markets with Matroid and Knapsack Constraints}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{141:1--141:14},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.141},
  URN =		{urn:nbn:de:0030-drops-62853},
  doi =		{10.4230/LIPIcs.ICALP.2016.141},
  annote =	{Keywords: Algorithmic mechanism design; Approximation algorithms; Matching under preferences; Matroid and knapsack constraints}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1340
Stackelberg Network Pricing Games

Authors: Patrick Briest, Martin Hoefer, and Piotr Krysta

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of $m$ priceable edges in a graph. The other edges have a fixed cost. Based on the leader's decision one or more followers optimize a polynomial-time solvable combinatorial minimization problem and choose a minimum cost solution satisfying their requirements based on the fixed costs and the leader's prices. The leader receives as revenue the total amount of prices paid by the followers for priceable edges in their solutions, and the problem is to find revenue maximizing prices. Our model extends several known pricing problems, including single-minded and unit-demand pricing, as well as Stackelberg pricing for certain follower problems like shortest path or minimum spanning tree. Our first main result is a tight analysis of a single-price algorithm for the single follower game, which provides a $(1+varepsilon) log m$-approximation for any $varepsilon >0$. This can be extended to provide a $(1+varepsilon )(log k + log m)$-approximation for the general problem and $k$ followers. The latter result is essentially best possible, as the problem is shown to be hard to approximate within $mathcal{O(log^varepsilon k + log^varepsilon m)$. If followers have demands, the single-price algorithm provides a $(1+varepsilon )m^2$-approximation, and the problem is hard to approximate within $mathcal{O(m^varepsilon)$ for some $varepsilon >0$. Our second main result is a polynomial time algorithm for revenue maximization in the special case of Stackelberg bipartite vertex cover, which is based on non-trivial max-flow and LP-duality techniques. Our results can be extended to provide constant-factor approximations for any constant number of followers.
Cite as

Patrick Briest, Martin Hoefer, and Piotr Krysta. Stackelberg Network Pricing Games. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 133-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{briest_et_al:LIPIcs.STACS.2008.1340,
  author =	{Briest, Patrick and Hoefer, Martin and Krysta, Piotr},
  title =	{{Stackelberg Network Pricing Games}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{133--142},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1340},
  URN =		{urn:nbn:de:0030-drops-13406},
  doi =		{10.4230/LIPIcs.STACS.2008.1340},
  annote =	{Keywords: Stackelberg Games, Algorithmic Pricing, Approximation Algorithms, Inapproximability.}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact