BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Yuval Emek

Yuval Emek appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingComputer Science and Game TheoryComputational GeometryDiscrete MathematicsMultiagent SystemsPopulations and Evolution

Catalog footprint

What is connected

15works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

15 published item(s)

preprint2023arXiv

Beeping Shortest Paths via Hypergraph Bipartite Decomposition

Constructing a shortest path between two network nodes is a fundamental task in distributed computing. This work develops schemes for the construction of shortest paths in randomized beeping networks between a predetermined source node and an arbitrary set of destination nodes. Our first scheme constructs a (single) shortest path to an arbitrary destination in $O (D \log\log n + \log^3 n)$ rounds with high probability. Our second scheme constructs multiple shortest paths, one per each destination, in $O (D \log^2 n + \log^3 n)$ rounds with high probability. Our schemes are based on a reduction of the above shortest path construction tasks to a decomposition of hypergraphs into bipartite hypergraphs: We develop a beeping procedure that partitions the (polynomially-large) hyperedge set of a hypergraph $H = (V_H, E_H)$ into $k = Θ(\log^2 n)$ disjoint subsets $F_1 \cup \cdots \cup F_k = E_H$ such that the (sub-)hypergraph $(V_H, F_i)$ is bipartite in the sense that there exists a vertex subset $U \subseteq V$ such that $|U \cap e| = 1$ for every $e \in F_i$. This procedure turns out to be instrumental in speeding up shortest path constructions under the beeping model.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Locally Restricted Proof Labeling Schemes (Full Version)

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 atesting proof labeling schemes (TPLS) (analogous to the type of relaxation used in property testing algorithms).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Communication Efficient Self-Stabilizing Leader Election (Full Version)

This paper presents a randomized self-stabilizing algorithm that elects a leader $r$ in a general $n$-node undirected graph and constructs a spanning tree $T$ rooted at $r$. The algorithm works under the synchronous message passing network model, assuming that the nodes know a linear upper bound on $n$ and that each edge has a unique ID known to both its endpoints (or, alternatively, assuming the $KT_{1}$ model). The highlight of this algorithm is its superior communication efficiency: It is guaranteed to send a total of $\tilde{O} (n)$ messages, each of constant size, till stabilization, while stabilizing in $\tilde{O} (n)$ rounds, in expectation and with high probability. After stabilization, the algorithm sends at most one constant size message per round while communicating only over the ($n - 1$) edges of $T$. In all these aspects, the communication overhead of the new algorithm is far smaller than that of the existing (mostly deterministic) self-stabilizing leader election algorithms. The algorithm is relatively simple and relies mostly on known modules that are common in the fault free leader election literature; these modules are enhanced in various subtle ways in order to assemble them into a communication efficient self-stabilizing algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Exploitation of Multiple Replenishing Resources with Uncertainty

We consider an optimization problem in which a (single) bat aims to exploit the nectar in a set of $n$ cacti with the objective of maximizing the expected total amount of nectar it drinks. Each cactus $i \in [n]$ is characterized by a parameter $r_{i} > 0$ that determines the rate in which nectar accumulates in $i$. In every round, the bat can visit one cactus and drink all the nectar accumulated there since its previous visit. Furthermore, competition with other bats, that may also visit some cacti and drink their nectar, is modeled by means of a stochastic process in which cactus $i$ is emptied in each round (independently) with probability $0 < s_i < 1$. Our attention is restricted to purely-stochastic strategies that are characterized by a probability vector $(p_1, \ldots, p_n)$ determining the probability $p_i$ that the bat visits cactus $i$ in each round. We prove that for every $ε> 0$, there exists a purely-stochastic strategy that approximates the optimal purely-stochastic strategy to within a multiplicative factor of $1 + ε$, while exploiting only a small core of cacti. Specifically, we show that it suffices to include at most $\frac{2 (1 - σ)}{ε\cdot σ}$ cacti in the core, where $σ= \min_{i \in [n]} s_{i}$. We also show that this upper bound on core size is asymptotically optimal as a core of a significantly smaller size cannot provide a $(1 + ε)$-approximation of the optimal purely-stochastic strategy. This means that when the competition is more intense (i.e., $σ$ is larger), a strategy based on exploiting smaller cores will be favorable.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Multicast Communications in Tree Networks with Heterogeneous Capacity Constraints

A widely studied problem in communication networks is that of finding the maximum number of communication requests that can be scheduled concurrently, subject to node and/or link capacity constraints. In this paper, we consider the problem of finding the largest number of multicast communication requests that can be serviced simultaneously by a network of tree topology, subject to heterogeneous capacity constraints. This problem generalizes the following two problems studied in the literature: a) the problem of finding a largest induced $k$-colorable subgraph of a chordal graph, b) the maximum multi-commodity flow problem in tree networks. The problem is already known to be NP-hard and to admit a $c$-approximation ($c \approx 1.58$) in the case of homogeneous capacity constraints. We first show that the problem is much harder to approximate in the heterogeneous case. We then use a generalization of a classical algorithm to obtain an $M$-approximation where $M$ is the maximum number of leaves of the subtrees representing the multicast communications. Surprisingly, the same algorithm, though in various disguises, is used in the literature at least four times to solve related problems (though the analysis is different). The special case of the problem where instances are restricted to unicast communications in a star topology network is known to be polynomial-time solvable. We extend this result and show that the problem can be solved in polynomial time for a set of paths in a tree that share a common vertex.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Stateful Posted Pricing with Vanishing Regret via Dynamic Deterministic Markov Decision Processes

In this paper, a rather general online problem called dynamic resource allocation with capacity constraints (DRACC) is introduced and studied in the realm of posted price mechanisms. This problem subsumes several applications of stateful pricing, including but not limited to posted prices for online job scheduling and matching over a dynamic bipartite graph. As the existing online learning techniques do not yield vanishing-regret mechanisms for this problem, we develop a novel online learning framework defined over deterministic Markov decision processes with dynamic state transition and reward functions. We then prove that if the Markov decision process is guaranteed to admit an oracle that can simulate any given policy from any initial state with bounded loss -- a condition that is satisfied in the DRACC problem -- then the online learning problem can be solved with vanishing regret. Our proof technique is based on a reduction to online learning with switching cost, in which an online decision maker incurs an extra cost every time she switches from one arm to another. We formally demonstrate this connection and further show how DRACC can be used in our proposed applications of stateful pricing.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Twenty-Two New Approximate Proof Labeling Schemes (Full Version)

Introduced by Korman, Kutten, and Peleg (Distributed Computing 2005), a \emph{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 \emph{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 \emph{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 \emph{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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Online Matching: Haste makes Waste!

This paper studies a new online problem, referred to as \emph{min-cost perfect matching with delays (MPMD)}, defined over a finite metric space (i.e., a complete graph with positive edge weights obeying the triangle inequality) $\mathcal{M}$ that is known to the algorithm in advance. Requests arrive in a continuous time online fashion at the points of $\mathcal{M}$ and should be served by matching them to each other. The algorithm is allowed to delay its request matching commitments, but this does not come for free: the total cost of the algorithm is the sum of metric distances between matched requests \emph{plus} the sum of times each request waited since it arrived until it was matched. A randomized online MPMD algorithm is presented whose competitive ratio is $O (\log^{2} n + \log Δ)$, where $n$ is the number of points in $\mathcal{M}$ and $Δ$ is its aspect ratio. The analysis is based on a machinery developed in the context of a new stochastic process that can be viewed as two interleaved Poisson processes; surprisingly, this new process captures precisely the behavior of our algorithm. A related problem in which the algorithm is allowed to clear any unmatched request at a fixed penalty is also addressed. It is suggested that the MPMD problem is merely the tip of the iceberg for a general framework of online problems with delayed service that captures many more natural problems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Space-Constrained Interval Selection

We study streaming algorithms for the interval selection problem: finding a maximum cardinality subset of disjoint intervals on the line. A deterministic 2-approximation streaming algorithm for this problem is developed, together with an algorithm for the special case of proper intervals, achieving improved approximation ratio of 3/2. We complement these upper bounds by proving that they are essentially best possible in the streaming setting: it is shown that an approximation ratio of $2 - ε$ (or $3 / 2 - ε$ for proper intervals) cannot be achieved unless the space is linear in the input size. In passing, we also answer an open question of Adler and Azar \cite{AdlerAzar03} regarding the space complexity of constant-competitive randomized preemptive online algorithms for the same problem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Semi-Streaming Set Cover

This paper studies the set cover problem under the semi-streaming model. The underlying set system is formalized in terms of a hypergraph $G = (V, E)$ whose edges arrive one-by-one and the goal is to construct an edge cover $F \subseteq E$ with the objective of minimizing the cardinality (or cost in the weighted case) of $F$. We consider a parameterized relaxation of this problem, where given some $0 \leq ε< 1$, the goal is to construct an edge $(1 - ε)$-cover, namely, a subset of edges incident to all but an $ε$-fraction of the vertices (or their benefit in the weighted case). The key limitation imposed on the algorithm is that its space is limited to (poly)logarithmically many bits per vertex. Our main result is an asymptotically tight trade-off between $ε$ and the approximation ratio: We design a semi-streaming algorithm that on input graph $G$, constructs a succinct data structure $\mathcal{D}$ such that for every $0 \leq ε< 1$, an edge $(1 - ε)$-cover that approximates the optimal edge \mbox{($1$-)cover} within a factor of $f(ε, n)$ can be extracted from $\mathcal{D}$ (efficiently and with no additional space requirements), where \[ f(ε, n) = \left\{ \begin{array}{ll} O (1 / ε), & \text{if } ε> 1 / \sqrt{n} \\ O (\sqrt{n}), & \text{otherwise} \end{array} \right. \, . \] In particular for the traditional set cover problem we obtain an $O(\sqrt{n})$-approximation. This algorithm is proved to be best possible by establishing a family (parameterized by $ε$) of matching lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Ants: Mobile Finite State Machines

Consider the Ants Nearby Treasure Search (ANTS) problem introduced by Feinerman, Korman, Lotker, and Sereni (PODC 2012), where $n$ mobile agents, initially placed at the origin of an infinite grid, collaboratively search for an adversarially hidden treasure. In this paper, the model of Feinerman et al. is adapted such that the agents are controlled by a (randomized) finite state machine: they possess a constant-size memory and are able to communicate with each other through constant-size messages. Despite the restriction to constant-size memory, we show that their collaborative performance remains the same by presenting a distributed algorithm that matches a lower bound established by Feinerman et al. on the run-time of any ANTS algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Signaling Schemes for Revenue Maximization

Signaling is an important topic in the study of asymmetric information in economic settings. In particular, the transparency of information available to a seller in an auction setting is a question of major interest. We introduce the study of signaling when conducting a second price auction of a probabilistic good whose actual instantiation is known to the auctioneer but not to the bidders. This framework can be used to model impressions selling in display advertising. We study the problem of computing a signaling scheme that maximizes the auctioneer's revenue in a Bayesian setting. While the general case is proved to be computationally hard, several cases of interest are shown to be polynomially solvable. In addition, we establish a tight bound on the minimum number of signals required to implement an optimal signaling scheme and show that at least half of the maximum social welfare can be preserved within such a scheme.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Stone Age Distributed Computing

The traditional models of distributed computing focus mainly on networks of computer-like devices that can exchange large messages with their neighbors and perform arbitrary local computations. Recently, there is a trend to apply distributed computing methods to networks of sub-microprocessor devices, e.g., biological cellular networks or networks of nano-devices. However, the suitability of the traditional distributed computing models to these types of networks is questionable: do tiny bio/nano nodes "compute" and/or "communicate" essentially the same as a computer? In this paper, we introduce a new model that depicts a network of randomized finite state machines operating in an asynchronous environment. Although the computation and communication capabilities of each individual device in the new model are, by design, much weaker than those of a computer, we show that some of the most important and extensively studied distributed computing problems can still be solved efficiently.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Approximating the Statistics of various Properties in Randomly Weighted Graphs

Consider the setting of \emph{randomly weighted graphs}, namely, graphs whose edge weights are chosen independently according to probability distributions with finite support over the non-negative reals. Under this setting, properties of weighted graphs typically become random variables and we are interested in computing their statistical features. Unfortunately, this turns out to be computationally hard for some properties albeit the problem of computing them in the traditional setting of algorithmic graph theory is tractable. For example, there are well known efficient algorithms that compute the \emph{diameter} of a given weighted graph, yet, computing the \emph{expected} diameter of a given randomly weighted graph is \SharpP{}-hard even if the edge weights are identically distributed. In this paper, we define a family of properties of weighted graphs and show that for each property in this family, the problem of computing the \emph{$k^{\text{th}}$ moment} (and in particular, the expected value) of the corresponding random variable in a given randomly weighted graph $G$ admits a \emph{fully polynomial time randomized approximation scheme (FPRAS)} for every fixed $k$. This family includes fundamental properties of weighted graphs such as the diameter of $G$, the \emph{radius} of $G$ (with respect to any designated vertex) and the weight of a \emph{minimum spanning tree} of $G$.

0 citations0 reviewsNo code linkedOpen access