4 Search Results for "Lidbetter, Thomas"


Document
A Local Search Algorithm for the Min-Sum Submodular Cover Problem

Authors: Lisa Hellerstein, Thomas Lidbetter, and R. Teal Witter

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)


Abstract
We consider the problem of solving the Min-Sum Submodular Cover problem using local search. The Min-Sum Submodular Cover problem generalizes the NP-complete Min-Sum Set Cover problem, replacing the input set cover instance with a monotone submodular set function. A simple greedy algorithm achieves an approximation factor of 4, which is tight unless P=NP [Streeter and Golovin, NeurIPS, 2008]. We complement the greedy algorithm with analysis of a local search algorithm. Building on work of Munagala et al. [ICDT, 2005], we show that, using simple initialization, a straightforward local search algorithm achieves a (4+ε)-approximate solution in time O(n³log(n/ε)), provided that the monotone submodular set function is also second-order supermodular. Second-order supermodularity has been shown to hold for a number of submodular functions of practical interest, including functions associated with set cover, matching, and facility location. We present experiments on two special cases of Min-Sum Submodular Cover and find that the local search algorithm can outperform the greedy algorithm on small data sets.

Cite as

Lisa Hellerstein, Thomas Lidbetter, and R. Teal Witter. A Local Search Algorithm for the Min-Sum Submodular Cover Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hellerstein_et_al:LIPIcs.ISAAC.2022.3,
  author =	{Hellerstein, Lisa and Lidbetter, Thomas and Witter, R. Teal},
  title =	{{A Local Search Algorithm for the Min-Sum Submodular Cover Problem}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{3:1--3:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.3},
  URN =		{urn:nbn:de:0030-drops-172880},
  doi =		{10.4230/LIPIcs.ISAAC.2022.3},
  annote =	{Keywords: Local search, submodularity, second-order supermodularity, min-sum set cover}
}
Document
Online Search with a Hint

Authors: Spyros Angelopoulos

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
The linear search problem, informally known as the cow path problem, is one of the fundamental problems in search theory. In this problem, an immobile target is hidden at some unknown position on an unbounded line, and a mobile searcher, initially positioned at some specific point of the line called the root, must traverse the line so as to locate the target. The objective is to minimize the worst-case ratio of the distance traversed by the searcher to the distance of the target from the root, which is known as the competitive ratio of the search. In this work we study this problem in a setting in which the searcher has a hint concerning the target. We consider three settings in regards to the nature of the hint: i) the hint suggests the exact position of the target on the line; ii) the hint suggests the direction of the optimal search (i.e., to the left or the right of the root); and iii) the hint is a general k-bit string that encodes some information concerning the target. Our objective is to study the Pareto-efficiency of strategies in this model. Namely, we seek optimal, or near-optimal tradeoffs between the searcher’s performance if the hint is correct (i.e., provided by a trusted source) and if the hint is incorrect (i.e., provided by an adversary).

Cite as

Spyros Angelopoulos. Online Search with a Hint. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{angelopoulos:LIPIcs.ITCS.2021.51,
  author =	{Angelopoulos, Spyros},
  title =	{{Online Search with a Hint}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{51:1--51:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.51},
  URN =		{urn:nbn:de:0030-drops-135902},
  doi =		{10.4230/LIPIcs.ITCS.2021.51},
  annote =	{Keywords: Search problems, searching on the line, competitive analysis, predictions}
}
Document
Computational Fun with Sturdy and Flimsy Numbers

Authors: Trevor Clokie, Thomas F. Lidbetter, Antonio J. Molina Lovett, Jeffrey Shallit, and Leon Witzman

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)


Abstract
Following Stolarsky, we say that a natural number n is flimsy in base b if some positive multiple of n has smaller digit sum in base b than n does; otherwise it is sturdy . We develop algorithmic methods for the study of sturdy and flimsy numbers. We provide some criteria for determining whether a number is sturdy. Focusing on the case of base b = 2, we study the computational problem of checking whether a given number is sturdy, giving several algorithms for the problem. We find two additional, previously unknown sturdy primes. We develop a method for determining which numbers with a fixed number of 0’s in binary are flimsy. Finally, we develop a method that allows us to estimate the number of k-flimsy numbers with n bits, and we provide explicit results for k = 3 and k = 5. Our results demonstrate the utility (and fun) of creating algorithms for number theory problems, based on methods of automata theory.

Cite as

Trevor Clokie, Thomas F. Lidbetter, Antonio J. Molina Lovett, Jeffrey Shallit, and Leon Witzman. Computational Fun with Sturdy and Flimsy Numbers. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{clokie_et_al:LIPIcs.FUN.2021.10,
  author =	{Clokie, Trevor and Lidbetter, Thomas F. and Molina Lovett, Antonio J. and Shallit, Jeffrey and Witzman, Leon},
  title =	{{Computational Fun with Sturdy and Flimsy Numbers}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.10},
  URN =		{urn:nbn:de:0030-drops-127715},
  doi =		{10.4230/LIPIcs.FUN.2021.10},
  annote =	{Keywords: sturdy number, flimsy number, context-free grammar, finite automaton, enumeration}
}
Document
The Expanding Search Ratio of a Graph

Authors: Spyros Angelopoulos, Christoph Dürr, and Thomas Lidbetter

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)


Abstract
We study the problem of searching for a hidden target in an environment that is modeled by an edge-weighted graph. Most of the previous work on this problem considers the pathwise cost formulation, in which the cost incurred by the searcher is the overall time to locate the target, assuming that the searcher moves at unit speed. More recent work introduced the setting of expanding search in which the searcher incurs cost only upon visiting previously unexplored areas of the graph. Such a paradigm is useful in modeling problems in which the cost of re-exploration is negligible (such as coal mining). In our work we study algorithmic and computational issues of expanding search, for a variety of search environments including general graphs, trees and star-like graphs. In particular, we rely on the deterministic and randomized search ratio as the performance measures of search strategies, which were originally introduced by Koutsoupias and Papadimitriou [ICALP 1996] in the context of pathwise search. The search ratio is essentially the best competitive ratio among all possible strategies. Our main objective is to explore how the transition from pathwise to expanding search affects the competitive analysis, which has applications to optimization problems beyond the strict boundaries of search problems.

Cite as

Spyros Angelopoulos, Christoph Dürr, and Thomas Lidbetter. The Expanding Search Ratio of a Graph. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{angelopoulos_et_al:LIPIcs.STACS.2016.9,
  author =	{Angelopoulos, Spyros and D\"{u}rr, Christoph and Lidbetter, Thomas},
  title =	{{The Expanding Search Ratio of a Graph}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.9},
  URN =		{urn:nbn:de:0030-drops-57109},
  doi =		{10.4230/LIPIcs.STACS.2016.9},
  annote =	{Keywords: Search games, randomized algorithms, competitive analysis, game theory}
}
  • Refine by Author
  • 2 Angelopoulos, Spyros
  • 2 Lidbetter, Thomas
  • 1 Clokie, Trevor
  • 1 Dürr, Christoph
  • 1 Hellerstein, Lisa
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Dynamic programming
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → Grammars and context-free languages
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 2 competitive analysis
  • 1 Local search
  • 1 Search games
  • 1 Search problems
  • 1 context-free grammar
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2016
  • 1 2020
  • 1 2021
  • 1 2022

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