DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2019.42

The Generalized Microscopic Image Reconstruction Problem

Authors: Amotz Bar-Noy, Toni Böhnlein, Zvi Lotker, David Peleg, and Dror Rawitz

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract

This paper presents and studies a generalization of the microscopic image reconstruction problem (MIR) introduced by Frosini and Nivat [Andrea Frosini and Maurice Nivat, 2007; Nivat, 2002]. Consider a specimen for inspection, represented as a collection of points typically organized on a grid in the plane. Assume each point x has an associated physical value l_x, which we would like to determine. However, it might be that obtaining these values precisely (by a surgical probe) is difficult, risky, or impossible. The alternative is to employ aggregate measuring techniques (such as EM, CT, US or MRI), whereby each measurement is taken over a larger window, and the exact values at each point are subsequently extracted by computational methods. In this paper we extend the MIR framework in a number of ways. First, we consider a generalized setting where the inspected object is represented by an arbitrary graph G, and the vector l in R^n assigns a value l_v to each node v. A probe centered at a vertex v will capture a window encompassing its entire neighborhood N[v], i.e., the outcome of a probe centered at v is P_v = sum_{w in N[v]} l_w. We give a criterion for the graphs for which the extended MIR problem can be solved by extracting the vector l from the collection of probes, P^- = {P_v | v in V}. We then consider cases where such reconstruction is impossible (namely, graphs G for which the probe vector P is inconclusive, in the sense that there may be more than one vector l yielding P). Let us assume that surgical probes (whose outcome at vertex v is the exact value of l_v) are technically available to us (yet are expensive or risky, and must be used sparingly). We show that in such cases, it may still be possible to achieve reconstruction based on a combination of a collection of standard probes together with a suitable set of surgical probes. We aim at identifying the minimum number of surgical probes necessary for a unique reconstruction, depending on the graph topology. This is referred to as the Minimum Surgical Probing problem (MSP). Besides providing a solution for the above problems for arbitrary graphs, we also explore the range of possible behaviors of the Minimum Surgical Probing problem by determining the number of surgical probes necessary in certain specific graph families, such as perfect k-ary trees, paths, cycles, grids, tori and tubes.

Cite as

Amotz Bar-Noy, Toni Böhnlein, Zvi Lotker, David Peleg, and Dror Rawitz. The Generalized Microscopic Image Reconstruction Problem. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ISAAC.2019.42,
  author =	{Bar-Noy, Amotz and B\"{o}hnlein, Toni and Lotker, Zvi and Peleg, David and Rawitz, Dror},
  title =	{{The Generalized Microscopic Image Reconstruction Problem}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{42:1--42:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.42},
  URN =		{urn:nbn:de:0030-drops-115382},
  doi =		{10.4230/LIPIcs.ISAAC.2019.42},
  annote =	{Keywords: Discrete mathematics, Combinatorics, Reconstruction algorithm, Image reconstruction, Graph spectra, Grid graphs}
}

Document

DOI: 10.4230/LIPIcs.STACS.2008.1331

Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental

Authors: Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz

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

Abstract

In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost (``buying price''), and cost proportional to the duration of the usage (``rental rate''). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best option at any point in time. Multislope Ski Rental is a natural generalization of the classical Ski Rental problem (where the only options are pure rent and pure buy), which is one of the fundamental problems of online computation. The Multislope Ski Rental problem is an abstraction of many problems where online decisions cannot be modeled by just two options, e.g., power management in systems which can be shut down in parts. In this paper we study randomized algorithms for Multislope Ski Rental. Our results include the best possible online randomized strategy for any additive instance, where the cost of switching from one option to another is the difference in their buying prices; and an algorithm that produces an $e$-competitive randomized strategy for any (non-additive) instance.

Cite as

Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 503-514, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{lotker_et_al:LIPIcs.STACS.2008.1331,
  author =	{Lotker, Zvi and Patt-Shamir, Boaz and Rawitz, Dror},
  title =	{{Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{503--514},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1331},
  URN =		{urn:nbn:de:0030-drops-13313},
  doi =		{10.4230/LIPIcs.STACS.2008.1331},
  annote =	{Keywords: Competitive analysis, ski rental, randomized algorithms}
}

Document

DOI: 10.4230/DagSemProc.07411.5

High Entropy Random Selection Protocols

Authors: Nikolai K. Vereshchagin, Harry Buhrman, Matthias Cristandl, Michal Koucky, Zvi Lotker, and Boaz Patt-Shamir

Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

Abstract

We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n - O(1) and has 4log^* n rounds, improving over the protocol of Goldwasser et al. that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n^2) bits of communication. Next we reduce the communication in our protocols. We show the existence, non-explicitly, of a protocol that has 6-rounds, 2n + 8log n bits of communication and yields entropy n- O(log n) and min-entropy n/2 - O(log n). Our protocol achieves the same entropy bound as the recent, also non-explicit, protocol of Gradwohl et al., however achieves much higher min-entropy: n/2 - O(log n) versus O(log n). Finally we exhibit very simple explicit protocols. We connect the security parameter of these geometric protocols with the well studied Kakeya problem motivated by harmonic analysis and analytical number theory. We are only able to prove that these protocols have entropy 3n/4 but still n/2 - O(log n) min-entropy. Therefore they do not perform as well with respect to the explicit constructions of Gradwohl et al. entropy-wise, but still have much better min-entropy. We conjecture that these simple protocols achieve n -o(n) entropy. Our geometric construction and its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols.

Cite as

Nikolai K. Vereshchagin, Harry Buhrman, Matthias Cristandl, Michal Koucky, Zvi Lotker, and Boaz Patt-Shamir. High Entropy Random Selection Protocols. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{vereshchagin_et_al:DagSemProc.07411.5,
  author =	{Vereshchagin, Nikolai K. and Buhrman, Harry and Cristandl, Matthias and Koucky, Michal and Lotker, Zvi and Patt-Shamir, Boaz},
  title =	{{High Entropy Random Selection Protocols}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.5},
  URN =		{urn:nbn:de:0030-drops-13091},
  doi =		{10.4230/DagSemProc.07411.5},
  annote =	{Keywords: Shannon entropy, Random string ds}
}

3 Search Results for "Lotker, Zvi"

The Generalized Microscopic Image Reconstruction Problem

Abstract

Cite as

Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental

Abstract

Cite as

High Entropy Random Selection Protocols

Abstract

Cite as

Thanks for your feedback!

Could not send message