6 citations · 8 across the 18 of their papers we have counts for
26 papers
Quiz Show Games: Searching with Bimodal Hiding
Mingshi Yao, Thomas Lidbetter, Melike Baykal-Gürsoy
We consider a quiz show game in which a contestant is presented with a sequence of questions. Each time the contestant answers a question correctly, she receives a prize and procee…
Optimal Pure Strategies for a Discrete Search Game
Thuy Bui, Thomas Lidbetter, Kyle Y. Lin
Consider a two-person zero-sum search game between a Hider and a Searcher. The Hider chooses to hide in one of discrete locations (or "boxes") and the Searcher chooses a search…
Improved Bound for the Gerver-Ramsey Collinearity Problem
Thomas F. Lidbetter
Let be a finite subset of . A vector sequence is an -walk if and only if is an element of for all . G…
Optimal Patrolling Strategies for Trees and Complete Networks
Thuy Bui, Thomas Lidbetter
We present solutions to a continuous patrolling game played on network. In this zero-sum game, an Attacker chooses a time and place to attack a network for a fixed amount of time.…
A Local Search Algorithm for the Min-Sum Submodular Cover Problem
Lisa Hellerstein, Thomas Lidbetter, R. Teal Witter
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 probl…
The Search and Rescue Game on a Cycle
Thomas Lidbetter, Yifan Xie
We consider a search and rescue game introduced recently by the first author. An immobile target or targets (for example, injured hikers) are hidden on a graph. The terrain is assu…
A Game Theoretic Approach to a Problem in Polymatroid Maximization
Lisa Hellerstein, Thomas Lidbetter
We consider the problem of maximizing the minimum (weighted) value of all components of a vector over a polymatroid. This is a special case of the lexicographically optimal base pr…
Continuous Patrolling Games
Steve Alpern, Thuy Bui, Thomas Lidbetter +1
We study a patrolling game played on a network , considered as a metric space. The Attacker chooses a point of (not necessarily a node) to attack during a chosen time interv…
A General Framework for Approximating Min Sum Ordering Problems
Felix Happach, Lisa Hellerstein, Thomas Lidbetter
We consider a large family of problems in which an ordering (or, more precisely, a chain of subsets) of a finite set must be chosen to minimize some weighted sum of costs. This fam…
Computational Aspects of Sturdy and Flimsy Numbers
Trevor Clokie, Thomas F. Lidbetter, Antonio Molina Lovett +2
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 devel…
Search and Delivery Man Problems: When Are Depth-First Paths Optimal?
Steve Alpern, Thomas Lidbetter
Let h be a probability measure on the nodes and arcs of a network Q, viewed either as the location of a hidden object to be found or as the continuous distribution of customers rec…
Competitive Search in a Network
Spyros Angelopoulos, Thomas Lidbetter
We study the classic problem in which a Searcher must locate a hidden point, also called the Hider in a network, starting from a root point. The network may be either bounded or un…
A Search Game on a Hypergraph with Booby Traps
Thomas Lidbetter, Kyle Lin
A set of n boxes, located on the vertices of a hypergraph G, contain known but different rewards. A Searcher opens all the boxes in some hyperedge of G with the objective of collec…
Search and Rescue in the Face of Uncertain Threats
Thomas Lidbetter
We consider a search problem in which one or more targets must be rescued by a search party, or Searcher. The targets may be survivors of some natural disaster, or prisoners held b…
Additive Number Theory via Approximation by Regular Languages
Jason Bell, Thomas Finn Lidbetter, Jeffrey Shallit
We prove some new theorems in additive number theory, using novel techniques from automata theory and formal languages. As an example of our method, we prove that every natural num…
Counting Subwords and Regular Languages
Charles J. Colbourn, Ryan E. Dougherty, Thomas F. Lidbetter +1
Let and be words. We consider the languages whose words are those for which the numbers of occurrences of and , as subwords of , are the same (resp., the numb…
Searching for Multiple Objects in Multiple Locations
Thomas Lidbetter, Kyle Lin
Many practical search problems concern the search for multiple hidden objects or agents, such as earthquake survivors. In such problems, knowing only the list of possible locations…
Bounds on the burning numbers of spiders and path-forests
Anthony Bonato, Thomas Lidbetter
Graph burning is one model for the spread of memes and contagion in social networks. The corresponding graph parameter is the burning number of a graph , written , which m…
Periodic Patrols on the Line and Other Networks
Steve Alpern, Thomas Lidbetter, Katerina Papadaki
We consider a patrolling game on a graph recently introduced by Alpern et al. (2011) where the Patroller wins if he is at the attacked node while the attack is taking place. This p…
Solving Zero-sum Games using Best Response Oracles with Applications to Search Games
Lisa Hellerstein, Thomas Lidbetter, Daniel Pirutinsky
We present efficient algorithms for computing optimal or approximately optimal strategies in a zero-sum game for which Player I has n pure strategies and Player II has an arbitrary…
A Variation on Chip-Firing: the diffusion game
C. Duffy, T. F. Lidbetter, M. E. Messinger +1
We introduce a natural variant of the parallel chip-firing game, called the diffusion game. Chips are initially assigned to vertices of a graph. At every step, all vertices simulta…
Constant Factor Approximate Solutions for Expanding Search on General Networks
Steve Alpern, Thomas Lidbetter
We study the classical problem introduced by R. Isaacs and S. Gal of minimizing the time to find a hidden point on a network moving from a known starting point. Rather than…
On Submodular Search and Machine Scheduling
Robbert Fokkink, Thomas Lidbetter, László A. Végh
Suppose some objects are hidden in a finite set of hiding places which must be examined one-by-one. The cost of searching subsets of is given by a submodular function and t…
The expanding search ratio of a graph
Spyros Angelopoulos, Christoph Dürr, Thomas Lidbetter
We study the problem of searching for a hidden target in an environment that is modeled by an edge-weighted graph. A sequence of edges is chosen starting from a given root vertex s…