Competitive Search in a Network

Spyros Angelopoulos; Thomas Lidbetter

REVIEW 3 major objections 6 minor 24 references

Competitive Search in a Network

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Waterfilling search is optimal; random doubling hits 5/4

desk verdict Core results are solid; abstract oversells the 5/4 factor, the Y-network table has a sign error, and the stress-test's Theorem 8 counterexample is a misreading. read the letter →

arxiv 1908.02132 v1 pith:6B5RWW73 submitted 2019-08-06 math.OC cs.DS

Spyros Angelopoulos , Thomas Lidbetter This is my paper · ORCID

classification math.OCcs.DS MSC 90B4091A0568W27

keywords searchgamesexpandingpathwisecompetitiveratiorandomizedstrategiesnetworkwaterfillingapproximationalgorithms

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how efficiently a Searcher can locate a hidden point in a network when the score is the competitive ratio, the worst-case ratio of discovery time to the Hider's true distance from the root, and it covers both bounded and unbounded networks. For expanding search, where movement over already explored territory is free, it proves that the optimal deterministic strategy is a pure waterfilling search that sweeps outward in distance layers from the root, with competitive ratio $\sup_{r>0} f_Q(r)/r$ where $f_Q(r)$ is the length of the network within distance $r$. The main new result is a randomized doubling strategy, formed by running randomized depth-first searches over randomly chosen distance bands, that approximates the randomized competitive ratio of every network within a factor of $5/4$, and a sibling strategy giving a $5$-approximation for the classical pathwise model. The paper also shows the deterministic-to-randomized gap can be as large as a factor of $2$, and that exact randomized optimal strategies are already intricate on a three-arc Y-shaped network.

What carries the argument

The load-bearing object is the family of distance discs $Q[r]=\{x:d(x)\le r\}$ and its measure $f_Q(r)$; the inverse $g_Q$ turns the discs into the waterfilling strategy $S^*(t)=Q[g_Q(t)]$, and the optimality proof is simply that any search must spend at least $f_Q(r)$ time before it can cover $Q[r]$. For the randomized results, the supporting machinery is a Hider strategy that hides with density proportional to distance on a connected set $A$, forcing $\rho\ge(\bar d(A)+\lambda(A)/2)/\bar d(A)$, and the randomized doubling strategy: partition a shortest-path tree into random bands $R_j$ with boundaries chosen uniformly in $[2^{j-1},2^j]$, then on each band run a randomized depth-first search, an equiprobable mixture of a DFS and its reverse. Lemma 13 bounds the expected discovery time inside a band, Lemma 14 converts the Hider lower bound into the band-measure inequality used in Theorem 16's calculation, and Lemma 15 computes the expected overlap between a band and its random boundary; the $5/4$ constant emerges from optimizing the resulting three-term expression in $d(x)/2^k$.

What would settle it

Take a rooted tree with two long branches and compute the worst-case expected normalized discovery time of the randomized doubling strategy for points just inside $2^k$; if the disconnected structure of $Q_k$ causes the quantity $E(L_J)/(d(x)\rho)$ from Theorem 16's proof to exceed $5/4$, the claimed bound $\rho_s\le 5\rho/4+1/2$ is false. This can be checked by dynamic programming over the tree or by direct simulation of the strategy.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is that the competitive ratio of expanding search is governed by the function $f_Q(r)$, the total measure of all points at distance at most $r$ from the root. The waterfilling search $S^*(t)=Q[g_Q(t)]$, which at time $t$ has explored exactly the set of points within distance $g_Q(t)$, is optimal among deterministic expanding searches, so the deterministic ratio is exactly $\sigma=\sup_{r>0} f_Q(r)/r$. Randomization changes the picture: the paper constructs Hider strategies that force $\rho\ge\sigma/2$, gives networks where this bound is tight, proves that for concave $f_Q$ the deterministic and randomized ratios coincide with the root degree, and exhibits a three-arc network whose optimal randomized strategy is a complicated mixture of four search orders. To escape that complexity, it proves that the randomized doubling strategy satisfies $\rho_s\le(5/4)\rho+1/2$, and that the same level-doubling construction yields a $5$-approximation for pathwise search, improving the previous $3+2\sqrt2\approx5.828$ approximation.

Load-bearing premise

The load-bearing technical premise is that the lower-bound argument may treat each distance band $Q_j=\{x:2^{j-1}\le d(x)<2^j\}$ as one connected region when applying the Hider-strategy bound of Theorem 8, even though on a multi-branch tree the band is a disjoint union of intervals; if componentwise summation is not justified, the $5/4$ and pathwise $5$ constants lose their proof.

Editorial extensions

If this is right

The deterministic expanding competitive ratio of any network is exactly computable as $\sup_{r>0} f_Q(r)/r$, so evaluating a network for search reduces to knowing its distance-measure function.
For networks whose distance-measure function $f_Q$ is concave (dense near the root, thinning outward), randomization buys nothing: $\sigma=\rho=\deg_Q(O)$ and waterfilling is optimal in both senses.
The randomized competitive ratio can be as small as half the deterministic one, so forbidding randomization can cost a factor of $2$ in guaranteed worst-case discovery time.
Any exact optimal randomized expanding strategy must, on some three-arc networks, mix between qualitatively different orders of searching the branches, so simple fixed-rule strategies cannot be exactly optimal in general.
The same random-band construction yields the first constant-factor approximation for randomized pathwise search on general networks, with factor $5$, improving the previous $3+2\sqrt2\approx5.828$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The $5/4$ constant is likely not the last word: for the line and the star, the structure of known optimal randomized strategies suggests the true worst-case benefit of randomization is milder, and the band-partition analysis could be sharpened on those restricted domains.
A concrete test of the proof's weakest point is to run the doubling strategy on a rooted tree with several long branches and check whether the disconnected distance bands $Q_j$ require a larger approximation constant than $5/4$; if the constant survives, the proof can likely be repaired by componentwise bookkeeping.
In practical terms, the implementation section implies the strategy's oracle cost is logarithmic in the Hider's distance, so on road-network-like inputs with approximately concave $f_Q$ the waterfilling strategy may already be near-optimal and need no randomization at all.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things you should know up front. First, the main results are real: the deterministic waterfilling optimality is clean, and the randomized doubling strategy gives the first constant-factor approximation for the randomized expanding-search ratio on general continuous networks, plus a pathwise 5-approximation that beats the standing 3+2√2 ≈ 5.828 bound. Second, the paper has two honest warts: the abstract claims a strict 5/4 approximation when Theorem 16 proves ρ_s ≤ (5/4)ρ + 1/2, and the Y-network optimality table in Section 4.3 contains a negative probability (e.g., L=1, M=2 gives -1/11 for strategy B) and doesn't always sum to 1. Those are fixable, but the printed version is wrong.

The stress-test note about Theorem 8 does not survive contact with the paper. It claims the lower bound T(S,u_A) ≥ d(A)+λ(A)/2 is false, using a two-ray star and setting d(A)=1/2. That misreads the notation. In the paper, d(A) in that inequality is the minimum distance from the root to A, which is 0 for the ball Q[1]; the average distance is a different quantity, though the text confusingly uses the same symbol for both. With minimum d, the inequality follows from a simple survival-probability integral, and it does not require A to be connected. So the connectedness worry about Lemma 14 also disappears — the bound is measure-theoretic.

What's good: Theorem 6's proof is short and correct; Lemma 10's degree bound and the concavity corollary are neat; the random-levels RDFS construction is genuinely inventive and, apart from the additive constant, the 5/4 analysis holds together. The pathwise adaptation in Theorem 19 is a real improvement and imports the expanding-search lower-bound technology in a natural way.

Who should read it: people working in search games, competitive analysis of online algorithms, and those interested in the expanding-search paradigm. It is not a blockbuster outside the subfield, but inside it, it answers open questions from the authors' own earlier work.

Verdict: the paper deserves a serious referee. The flaws are local — an abstract overstatement and a mistaken probability table — and both are repairable without touching the core arguments. I would send it to peer review and ask for a revision on those two points.

Referee Report

3 major / 6 minor

Summary. The paper studies deterministic and randomized search games on a connected network, with a root O, under a competitive-ratio objective. For expanding search, it proposes the waterfilling strategy S*(t)=Q[g_Q(t)] and proves that it achieves the optimal deterministic competitive ratio sigma = sup_{r>0} f_Q(r)/r. For randomized expanding search, it gives the bound sigma/2 <= rho <= sigma, a Hider-strategy lower-bound tool, and a randomized doubling strategy that is claimed to be a 5/4-approximation of the randomized competitive ratio; it also analyzes exact optimal strategies on a three-arc Y-network. For pathwise search, it adapts the doubling strategy to obtain a claimed 5-approximation of the randomized competitive ratio, improving on the earlier 3+2*sqrt(2) factor.

Significance. The waterfilling optimality theorem and the sigma/2 <= rho <= sigma bounds are clean and correct, and the randomized doubling framework is a genuinely new approach to general, possibly unbounded networks. If the central approximation theorems were fully correct, the paper would make a solid contribution to the competitive-search literature: it gives the first constant-factor randomized approximation for expanding search on general networks and improves pathwise search. However, the proof of the main 5/4-approximation rests on Theorem 8, whose stated inequality is false, and the Y-network section contains algebraic and probabilistic errors. The identified correction to Theorem 8 appears to repair the main doubling argument, so the paper's core idea is defensible, but the manuscript as written does not establish its headline claims.

major comments (3)

[Section 4.2, Theorem 8] The lower bound T(S,u_A) >= d(A) + lambda(A)/2 asserted in the proof of Theorem 8 is false. For the two-ray star with unit arcs and A=Q[1], we have lambda(A)=2 and d(A)=1/2, while the waterfilling search S*(t)=Q[t/2] gives T(S*,u_A)=1, so the claimed bound 3/2 is violated. The correct universal bound is T(S,u_A) >= lambda(A)/2, obtained by writing T(S,u_A) as the integral of the survival probability and using lambda(S(t) intersect A) <= t. The theorem should therefore state rho >= lambda(A)/(2 d(A)). This corrected form is exactly what Lemma 10 and Lemma 14 use, and being measure-theoretic it also removes the need for the sets Q_j in Lemma 14 to be connected. As printed, the proof of Lemma 10 already applies the corrected form rather than the stated theorem, so the manuscript is internally inconsistent.
[Section 4.3, Eq. (5) and Table 1] The lower-bound calculation for the Y-network is algebraically wrong. Substituting d(A)=1+(x^2+y^2)/(2(x+y)) and lambda(A)=x+y into (d(A)+lambda(A)/2)/d(A) yields 1+(x+y)^2/(2(x+y)+x^2+y^2), not the displayed 1+2xy/(x(x+2)+y(y+2)); the manuscript's numerator 1+(x+y)/2 omits the (x^2+y^2)/(2(x+y)) part of d(A). In addition, Table 1 assigns a negative probability to strategy B whenever M^2 > L^2+2L, for example L=1 and M=10 gives numerator 1+2-100=-97, so the proposed mixture is not a valid randomized strategy. Consequently the claimed exact value V and the statement that optimal randomized strategies are complex even on three-arc networks are not established as written.
[Abstract and Theorem 16] The abstract and the introduction describe the randomized doubling strategy as a 5/4-approximation of the randomized competitive ratio, but Theorem 16 proves only rho_s <= (5/4)rho + 1/2. For a network with small rho, such as a single ray where rho=1, the bound gives 1.75, not 1.25. If the intended approximation notion permits an additive constant, that notion should be defined and stated precisely; as written, the claim 'within a factor at most 5/4' is stronger than what is proved.

minor comments (6)

[Definition 1] There is a typo: 'we will refer to an expanding search as a search search strategy' should read 'as a search strategy.'
[Section 4.2, first paragraph] The notation d(A) is used both for the distance from O to A and for the average distance from O to points in A; these should be denoted by different symbols throughout.
[Lemma 13, proof] The expression S(t1) intersect S(ts) should be S(t1) intersect S(t2).
[Table 1] The probabilities and search descriptions use M in rows A, B, and D even though M' = max{M, sqrt(L(L+2))} was defined for the strategy; the table should be restated consistently in terms of M'.
[Section 4.3] The derivation of the Y-network lower bound would benefit from a displayed formula for d(A) in terms of x and y; the current omission appears to be the source of the algebraic error in Eq. (5).
[References] The reference 'Angelopoulos, S., , Arsénio, D., Dürr, C., & López-Ortiz, A.' contains a stray comma after the first author's name and should be cleaned up.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the central bounds are derived in-paper; the few self-citations are explicitly flagged and come with full proofs, so they are not load-bearing.

full rationale

I walked the derivation chain and found no step in which a claimed prediction reduces by construction to its own input. The deterministic waterfilling result (Theorem 6) is proved in-paper: for an arbitrary search S, t(r) is defined as the first time Q[r] is covered, so t(r) ≥ fQ(r), while for S*(t)=Q[gQ(t)] one has t*(r)=fQ(r). Thus σ = sup fQ(r)/r follows from the definitions, not from an assumed conclusion. The randomized lower bounds (Proposition 7, Theorem 8, Lemma 10, Lemma 14) are derived from explicit Hider distributions and measure inequalities: for example, hiding uniformly on Q[r] gives expected search time at least λ(Q[r])/2, and the averaging in Theorem 8 is a direct calculation from the density dh_A(x)=d(x)du_A(x)/d(A). Lemma 14 is an algebraic consequence of the lower bound ρ ≥ λ(A)/(2d(A)) and the quadratic maximization. The 5/4-approximation Theorem 16 is built from Lemmas 13–15, all proved in the paper from the definition of the random levels R_j and the RDFS property; no fitted parameter is renamed as a prediction. The pathwise 5-approximation Theorem 19 reuses the E(LJ) bound proved in Theorem 16, again by explicit summation. The self-citations to Angelopoulos, Dürr and Lidbetter (2016, 2019) are not load-bearing: the paper explicitly states that Theorem 6 and Proposition 7 'appeared without proof' in the earlier work and then supplies the proofs here, and the doubling strategy is only described as 'inspired by' the earlier discrete-tree strategy, not justified by it. A possible correctness concern about Theorem 8 (the stated lower bound T(S,u_A) ≥ d(A)+λ(A)/2 may be false for a two-ray star with A=Q[1]) is a mathematical-error issue, not circularity: even if the bound were corrected to λ(A)/2, the lower-bound argument would still be derived from the Hider construction rather than assumed from the target theorem.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central results rest on the expanding-search model, the bounded-branching condition, the minimax value of the game, and the transfer to the shortest path tree. No data fitting or invented physical entities appear; the only tuned constant is the ratio r=1+sqrt(2), which does not affect the main theorems.

free parameters (1)

Geometric ratio r in Chinese Postman pathwise strategy = 1 + sqrt(2)
Chosen in Theorem 17 to minimize 2(r/(r-1)+r/2); a tunable analysis parameter not used in the main 5/4 or 5 theorems.

assumptions (5)

domain assumption Network Q has at most M points at any distance r from root (condition (1)).
Section 2 standing assumption; guarantees finite competitive ratio and fQ(r)≤Mr.
domain assumption Expanding search is a family of connected sets S(t) with λ(S(t))=t (Definition 1).
Defines the model; all expanding-search results rely on it.
standard math The search game has a value equal to the randomized competitive ratio via the Alpern-Gal minimax theorem.
Invoked in Theorem 4 and in the Hider lower bounds of Section 4.2.
domain assumption For uniform hider distribution on a connected set A, expected search time is at least d(A)+λ(A)/2.
Stated without proof in Theorem 8; a known property of expanding search used to derive lower bounds.
domain assumption The shortest path tree QT covers all points of Q and preserves distances from the root, so a search of QT is a valid search of Q.
Section 4.4 defines the random levels over QT; the paper does not explicitly prove the transfer, though it is standard for shortest path trees.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Competitive Search in a Network." pith.science (2026). https://pith.science/paper/6B5RWW73

@misc{pith2026190802132,
  author       = {Pith},
  title        = {Pith review of: Competitive Search in a Network},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6B5RWW73}},
  note         = {Machine review of arXiv:1908.02132}
}

read the original abstract

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 unbounded, thus generalizing well-known settings such as linear and star search. We distinguish between pathwise search, in which the Searcher follows a continuous unit-speed path until the Hider is reached, and expanding search, in which, at any point in time, the Searcher may restart from any previously reached point. The former has been the usual paradigm for studying search games, whereas the latter is a more recent paradigm that can model real-life settings such as hunting for a fugitive, demining a field, or search-and-rescue operations. We seek both deterministic and randomized search strategies that minimize the competitive ratio, namely the worst-case ratio of the Hider's discovery time, divided by the shortest path to it from the root. Concerning expanding search, we show that a simple search strategy that applies a "waterfilling" principle has optimal deterministic competitive ratio; in contrast, we show that the optimal randomized competitive ratio is attained by fairly complex strategies even in a very simple network of three arcs. Motivated by this observation, we present and analyze an expanding search strategy that is a 5/4 approximation of the randomized competitive ratio. Our approach is also applicable to pathwise search, for which we give a strategy that is a 5 approximation of the randomized competitive ratio, and which improves upon strategies derived from previous work.

Figures

Figures reproduced from arXiv: 1908.02132 by the authors.

**Figure 1.** An illustration of different search domains. et al., 2019) recently studied expanding search in a fixed (finite) graph in which the Hider can only hide on vertices. In terms of finding a strategy of optimal deterministic competitive ratio (Angelopoulos et al., 2019) showed that the problem is NP-hard, and gave a 4 ln 4 approximation. Concerning the randomized competitive ratio, the same work presented a strategy tha… view at source ↗

**Figure 2.** A network for which ρ ≈ σ/2. A corollary of Proposition 7 is that the “water-filling” search S ∗ approximates the optimal randomized search by a factor of 2. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** An example of a network Q (left) and the function r 7→ f(r) ≡ fQ(r) (right). All arcs in Q are unit-length. More generally, we have established the following approximation. Corollary 12. Suppose that for the network Q it holds that supr>0 fQ(r)/r ≤ α degQ(O), for some α > 1. Then S ∗ approximates the optimal randomized ratio of Q within a factor of at most α. 11 [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: The Y -network. Clearly the optimal Hider strategy on the Y -network will hide on the arc incident to the root with probability 0. Let A be the subset of Q consisting of all the points on the left arc at distance at most x from v and all the points on the right arc at …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

Alpern, S., & Gal, S. (1988). A mixed strategy minimax theorem without compactness.SIAM Journal on Control and Optimization, 26(6), 1357-1361

work page 1988
[2]

(2003).The theory of search games and rendezvous

Alpern, S., & Gal, S. (2003).The theory of search games and rendezvous. Kluwer Academic Publishers

work page 2003
[3]

Alpern, S., & Lidbetter, T. (2013). Mining coal or ﬁnding terrorists: The expanding search paradigm. Operations Research, 61(2), 265–279

work page 2013
[4]

Alpern, S., & Lidbetter, T. (2019). Approximate solutions for expanding search games on general networks. Annals of Operations Research, 275, 259–279

work page 2019
[5]

Angelopoulos, S., , Arsénio, D., Dürr, C., & López-Ortiz, A. (2016). Multi-processor search and scheduling problems with setup cost.Theory of Computing Systems, 1–34

work page 2016
[6]

Angelopoulos, S., Arsénio, D., & Dürr, C. (2017). Inﬁnite linear programming and online searching with turn cost. Theoretical Computer Science, 670, 11–22

work page 2017
[7]

Angelopoulos, S., Dürr, C., & Lidbetter, T. (2016). The expanding search ratio of a graph. InProceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (stacs)(pp. 9:1– 9:14)

work page 2016
[8]

Angelopoulos, S., Dürr, C., & Lidbetter, T. (2019). The expanding search ratio of a graph. Discrete Applied Mathematics, 260, 51–65

work page 2019

Show all 24 references

[9]

Angelopoulos, S., López-Ortiz, A., & Panagiotou, K. (2014). Multi-target ray searching problems.Theo- retical Computer Science, 540, 2–12

2014
[10]

Ausiello, G., Leonardi, S., & Marchetti-Spaccamela, A. (2000). On salesmen, repairmen, spiders, and other traveling agents. InProceedings of 4th Italian Conference on Algorithms and Complexity, CIAC(pp. 1–16)

2000
[11]

Beck, A., & Newman, D. (1970). Yet more on the linear search problem.Israel Journal of Mathematics, 8, 419–429

1970
[12]

D., & Durocher, S

Bose, P., Carufel, J. D., & Durocher, S. (2015). Searching on a line: A complete characterization of the optimal solution. Theoretical Computer Science, 569, 24–42

2015
[13]

Demaine, E., Fekete, S., & Gal, S. (2006). Online searching with turn cost.Theoretical Computer Science, 361, 342-355

2006
[14]

Fleischer, R., Kamphans, T., Klein, R., Langetepe, E., & Trippen, G. (2008). Competitive online approx- imation of the optimal search ratio.SIAM Journal on Computing, 38(3), 881-898

2008
[15]

Gal, S. (1972). A general search game.Israel Journal of Mathematics, 12, 32–45

1972
[16]

Gal, S. (1974). Minimax solutions for linear search problems.SIAM Journal on Applied Mathematics, 27, 17–30

1974
[17]

Gal, S. (1979). Search games with mobile and immobile hider.SIAM Journal on Control and Optimization, 17(1), 99–122

1979
[18]

A., Icking, C., Klein, R., & Langetepe, E

Hipke, C. A., Icking, C., Klein, R., & Langetepe, E. (1999). How to ﬁnd a point on a line within a ﬁxed distance. Discrete Applied Mathematics, 93(1), 67–73

1999
[19]

(1965).Diﬀerential games

Isaacs, R. (1965).Diﬀerential games. John Wiley and Sons, New York

1965
[20]

Jaillet, P., & Staﬀord, M. (1993). Online searching.Operations Research, 49, 234–244. 20

1993
[21]

Kao, M.-Y., Ma, Y., Sipser, M., & Yin, Y. (1998). Optimal constructions of hybrid algorithms.Journal of Algorithms, 29(1), 142–164

1998
[22]

Kirkpatrick, D. G. (2009). Hyperbolic dovetailing. In Proceedings of the 17th European Symposium on Algorithms (ESA)(pp. 616–627)

2009
[23]

Koutsoupias, E., Papadimitriou, C., & Yannakakis, M. (1996). Searching a ﬁxed graph. InProceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP)(p. 280- 289). López-Ortiz, A., & Schuierer, S. (2001). The ultimate strategy to search onm ray...

1996
[24]

McGregor, A., Onak, K., & Panigrahy, R. (2009). The oil searching problem. InProceedings of the 17th European Symposium on Algorithms (ESA)(pp. 504–515). 21

2009

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Alpern, S., & Gal, S. (1988). A mixed strategy minimax theorem without compactness.SIAM Journal on Control and Optimization, 26(6), 1357-1361

work page 1988

[2] [2]

(2003).The theory of search games and rendezvous

Alpern, S., & Gal, S. (2003).The theory of search games and rendezvous. Kluwer Academic Publishers

work page 2003

[3] [3]

Alpern, S., & Lidbetter, T. (2013). Mining coal or ﬁnding terrorists: The expanding search paradigm. Operations Research, 61(2), 265–279

work page 2013

[4] [4]

Alpern, S., & Lidbetter, T. (2019). Approximate solutions for expanding search games on general networks. Annals of Operations Research, 275, 259–279

work page 2019

[5] [5]

Angelopoulos, S., , Arsénio, D., Dürr, C., & López-Ortiz, A. (2016). Multi-processor search and scheduling problems with setup cost.Theory of Computing Systems, 1–34

work page 2016

[6] [6]

Angelopoulos, S., Arsénio, D., & Dürr, C. (2017). Inﬁnite linear programming and online searching with turn cost. Theoretical Computer Science, 670, 11–22

work page 2017

[7] [7]

Angelopoulos, S., Dürr, C., & Lidbetter, T. (2016). The expanding search ratio of a graph. InProceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (stacs)(pp. 9:1– 9:14)

work page 2016

[8] [8]

Angelopoulos, S., Dürr, C., & Lidbetter, T. (2019). The expanding search ratio of a graph. Discrete Applied Mathematics, 260, 51–65

work page 2019