We study the Patrol Security Game (PSG), a robotic patrolling problem formulated as an extensive-form Stackelberg game, in which the attacker strategically selects the timing, location, and duration of an attack. The defender’s goal is to compute an infinite-horizon patrolling policy that minimizes the attacker’s expected payoff. By restricting the defender’s strategy to a time-homogeneous first-order Markov chain, we show that PSG can be reformulated as a combinatorial minimax problem. We prove that the optimal strategy under zero-penalty scenarios corresponds to minimizing either the expected hitting time or return time, depending on the attacker’s visibility model. These optimal policies are closed-form and can be computed efficiently. On the other hand, in high-penalty cases, we observe that the patrolling schedule with high randomness can minimize the attacker’s expected gain. However, in general, the minimax objective becomes non-convex. To address this, we introduce a bi-criteria optimization framework that jointly considers the expected maximum reward (EMR) and entropy rate of the patrolling policy. We propose three graph-based algorithms and a deep reinforcement learning model to efficiently balance these two objectives. Each algorithm demonstrates distinct strengths under different configurations, such as varying penalty scales and cost function settings. The extensive experiments on both synthetic and real-world crime datasets validate the effectiveness of our approaches, demonstrating superior performance and scalability compared to state-of-the-art baselines.

A determinacy race occurs if two or more logically parallel instructions access the same memory location and at least one of them tries to modify its content. Races are often undesirable as they can lead to nondeterministic and incorrect program behavior. A data race is a special case of a determinacy race which can be eliminated by associating a mutual-exclusion lock with the memory location in question or allowing atomic accesses to it. However, such solutions can reduce parallelism by serializing all accesses to that location. For associative and commutative updates to a memory cell, one can instead use a reducer, which allows parallel race-free updates at the expense of using some extra space. More extra space usually leads to more parallel updates, which in turn contributes to potentially lowering the overall execution time of the program. We start by asking the following question. Given a fixed budget of extra space for mitigating the cost of races in a parallel program, which memory locations should be assigned reducers and how should the space be distributed among those reducers in order to minimize the overall running time? We argue that under reasonable conditions the races of a program can be captured by a directed acyclic graph (DAG), with nodes representing memory cells and arcs representing read-write dependencies between cells. We then formulate our original question as an optimization problem on this DAG. We concentrate on a variation of this problem where space reuse among reducers is allowed by routing every unit of extra space along a (possibly different) source to sink path of the DAG and using it in the construction of multiple (possibly zero) reducers along the path. We consider two different ways of constructing a reducer and the corresponding duration functions (i.e., reduction time as a function of space budget). We generalize our race-avoiding space-time tradeoff problem to a discrete resource-time tradeoff problem with general non-increasing duration functions and resource reuse over paths of the given DAG. For general DAGs, we show that even if the entire DAG is available offline the problem is strongly NP-hard under all three duration functions, and we give approximation algorithms for solving the corresponding optimization problems. We also prove hardness of approximation for the general resource-time tradeoff problem and give a pseudo-polynomial time algorithm for series-parallel DAGs.