In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori and the edges arrive one at a time. The goal is to maintain a fractional vertex cover of the tree, i.e., an assignment of fractional weights from [0,1] to the vertices such that the weights of endpoints of every edge sum up to at least one. After each edge arrival, we need to modify the fractional vertex cover to cover the new edge as well. However, we can only increase the values assigned to vertices. The problem was studied before (in the vertex arrival model) by Wang and Wong, who motivated it as a generalization of the ski-rental problem, but also (more importantly) by its close connection to the dual online matching problem. They presented a 1.901-competitive algorithm for general graphs in the vertex arrival model. We present an 11/6 ≈ 1.83-competitive algorithm for trees in the more general edge arrival model. In addition, we study the fractional vertex cover problem in an incremental model, where we again seek a fractional vertex cover after every update, but all the updates to the tree are known to the algorithm a priori. In this model, we give a 1.5-competitive algorithm and provide a matching lower bound.

We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of the ordering yields a good solution for its respective cardinality. A classical result in this setting is that the greedy algorithm achieves a competitive ratio, i.e., an approximation guarantee across all cardinalities, of e/(e-1) ≈ 1.582. No better general guarantee was previously known. We present an adaptive scaling algorithm achieving a competitive ratio of 1.373. We complement our result by a lower bound of 1.25 on the best possible deterministic competitive ratio for incremental submodular maximization.

We prove that the active-set method needs an exponential number of iterations in the worst-case to maximize a convex quadratic function subject to linear constraints, regardless of the pivot rule used. This substantially improves over the best previously known lower bound [IPCO 2025], which needs objective functions of polynomial degrees \(\omega(\log d)\) in dimension \(d\), to a bound using a convex polynomial of degree 2. In particular, our result firmly resolves the open question [IPCO 2025] of whether a constant degree suffices, and it represents significant progress towards linear objectives, where the active-set method coincides with the simplex method and a lower bound for all pivot rules would constitute a major breakthrough.

The existence of a polynomial pivot rule for the simplex method for linear programming, policy iteration for Markov decision processes, and strategy improvement for parity games each are prominent open problems in their respective fields. While numerous natural candidates for efficient rules have been eliminated, all existing lower bound constructions are tailored to individual or small sets of pivot rules. We introduce a unified framework for formalizing classes of rules according to the information about the input that they rely on. Within this framework, we show lower bounds for ranking-based classes of rules that base their decisions on orderings of the improving pivot steps induced by the underlying data. Our first result is a superpolynomial lower bound for strategy improvement, obtained via a family of sink parity games, which applies to memory-based generalizations of Bland's rule that only access the input by comparing the ranks of improving edges in some global order. Our second result is a subexponential lower bound for policy iteration, obtained via a family of Markov decision processes, which applies to memoryless rules that only access the input by comparing improving actions according to their ranks in a global order, their reduced costs, and the associated improvements in objective value. Both results carry over to the simplex method for linear programming.

We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the performance of the particular exploration algorithm and the existence of light spanners. Conversely, we exploit this connection to construct light spanners of bounded genus graphs. In particular, we achieve a lightness that improves on the best known upper bound for genus g ≥ 1 and recovers the known tight bound for the planar case ( g = 0 ).

Abstract. In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time. We improve on the best known upper bounds on the competitive ratio on general metric spaces and on the half-line, for both the preemptive and nonpreemptive version of the problem. We achieve this by presenting a new algorithm called [Formula: see text]. More precisely, we show that it has competitive ratio 2.457 on general metric spaces and 2.366 on the half-line. This is the first upper bound that beats known lower bounds of 2.5 for schedule-based algorithms as well as the natural [Formula: see text] algorithm. Furthermore, we provide matching lower bounds on the competitive ratio of [Formula: see text], which yields that our analysis is tight.

We study the online service with deadlines (or delays) problem, in which a server must serve requests for points in a metric space while balancing travel distance and promptness of service. While the problem has been extensively studied (STOC 2017), (FOCS 2019), (FOCS 2023), the main open question whether a constant competitive ratio can be achieved remains wide open. We prove a logarithmic lower bound for a natural class of algorithms already on uniform line metrics. Our lower bound applies to, and is tight for, the best known algorithms for general metrics and uniform line metrics.

Abstract We introduce a framework for incremental–decremental maximization that captures the gradual transformation or renewal of infrastructures. In our model, an initial solution is transformed one element at a time and the utility of an intermediate solution is given by the sum of the utilities of the transformed and untransformed parts. We propose a simple randomized algorithm and a more sophisticated deterministic algorithm, both of which find an order in which to transform the elements while maintaining a large utility during all stages of transformation, relative to an optimal solution for the current stage. More specifically, our algorithms yield competitive solutions for utility functions of bounded curvature and/or generic submodularity ratio, and, in particular, for submodular functions and functions satisfying the gross substitutes property. Our results show that incremental–decremental maximization is substantially more difficult than incremental maximization.

In the Tricolored Euclidean Traveling Salesperson problem, we are given~$k=3$ sets of points in the plane and are looking for disjoint tours, each covering one of the sets. Arora (1998) famously gave a PTAS based on ``patching'' for the case $k=1$ and, recently, Dross et al.~(2023) generalized this result to~$k=2$. Our contribution is a $(5/3+ε)$-approximation algorithm for~$k=3$ that further generalizes Arora's approach. It is believed that patching is generally no longer possible for more than two tours. We circumvent this issue by either applying a conditional patching scheme for three tours or using an alternative approach based on a weighted solution for $k=2$.

We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously approximates the optimum for all budgets, we show that a bicriterial $(α,μ)$-approximation is possible, i.e., a solution that with budget $B+α$ for all $B \in \mathbb{R}_{\geq 0}$ is a multiplicative $μ$-approximation compared to the optimum solution with budget $B$. For the case that the underlying graph is a tree, we present a polynomial-time density-greedy algorithm that computes a $(χ,1)$-approximation, where $χ$ denotes the eccentricity of the root vertex in the underlying graph, and show that this is best possible. An adaptation of the density-greedy algorithm for general graphs is $(γ,2)$-competitive where $γ$ is the maximal length of a vertex-disjoint path starting in the root. While this algorithm does not run in polynomial time, it can be adapted to a $(γ,3)$-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a $(3χ,8)$-approximation and, more generally, a $\smash{\bigl((4\ell - 1)χ, \frac{2^{\ell + 2}}{2^{\ell}-1}\bigr)}$-approximation for every fixed $\ell \in \mathbb{N}$.

Abstract. We consider the problem of maximizing a fractionally subadditive function under an increasing knapsack constraint. An incremental solution to this problem is given by an order in which to include the elements of the ground set, and the competitive ratio of an incremental solution is defined by the worst ratio over all capacities relative to an optimum solution of the corresponding capacity. We present an algorithm that finds an incremental solution of competitive ratio at most [Formula: see text], under the assumption that the values of singleton sets are in the range [Formula: see text], and we give a lower bound of [Formula: see text] on the attainable competitive ratio. In addition, we establish that our framework captures potential-based flows between two vertices, and we give a lower bound of [Formula: see text] and an upper bound of [Formula: see text] for the incremental maximization of classical flows with capacities in [Formula: see text] which is tight for the unit capacity case.

Abstract. We consider classes of objective functions of cardinality-constrained maximization problems for which the greedy algorithm guarantees a constant approximation. We propose the new class of [Formula: see text]-[Formula: see text]-augmentable functions and prove that it encompasses several important subclasses, such as functions of bounded submodularity ratio, [Formula: see text]-augmentable functions, and weighted rank functions of an independence system of bounded rank quotient—as well as additional objective functions for which the greedy algorithm yields an approximation. For this general class of functions, we show a tight bound of [Formula: see text] on the approximation ratio of the greedy algorithm that tightly interpolates between bounds from the literature for functions of bounded submodularity ratio and for [Formula: see text]-augmentable functions. In particular, as a by-product, we close a gap in [A. Bernstein et al., Math. Program., 191 (2022), pp. 953–979] by obtaining a tight lower bound for [Formula: see text]-augmentable functions for all [Formula: see text]. For weighted rank functions of independence systems, our tight bound becomes [Formula: see text], which recovers the known bound of [Formula: see text] for independence systems of rank quotient at least [Formula: see text].

We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the performance of the particular exploration algorithm Blocking and the existence of light spanners. Conversely, we exploit this connection to construct light spanners of bounded genus graphs. In particular, we achieve a lightness that improves on the best known upper bound for genus g>0 and recovers the known tight bound for the planar case (g=0).

We consider the problem of finding an incremental solution to a cardinality-constrained maximization problem that not only captures the solution for a fixed cardinality, but also describes how to gradually grow the solution as the cardinality bound increases. The goal is to find an incremental solution that guarantees a good competitive ratio against the optimum solution for all cardinalities simultaneously. The central challenge is to characterize maximization problems where this is possible, and to determine the best-possible competitive ratio that can be attained. A lower bound of 2.18 and an upper bound of φ + 1 ≈ 2.618 are known on the competitive ratio for monotone and accountable objectives [Bernstein et al., Math. Prog., 2022], which capture a wide range of maximization problems. We introduce a continuization technique and identify an optimal incremental algorithm that provides strong evidence that φ+1 is the best-possible competitive ratio. Using this continuization, we obtain an improved lower bound of 2.246 by studying a particular recurrence relation whose characteristic polynomial has complex roots exactly beyond the lower bound. Based on the optimal continuous algorithm combined with a scaling approach, we also provide a 1.772-competitive randomized algorithm. We complement this by a randomized lower bound of 1.447 via Yao’s principle.

We construct a family of Markov decision processes for which the policy iteration algorithm needs an exponential number of improving switches with Dantzig's rule, with Bland's rule, and with the Largest Increase pivot rule. This immediately translates to a family of linear programs for which the simplex algorithm needs an exponential number of pivot steps with the same three pivot rules. Our results yield a unified construction that simultaneously reproduces well-known lower bounds for these classical pivot rules, and we are able to infer that any (deterministic or randomized) combination of them cannot avoid an exponential worst-case behavior. Regarding the policy iteration algorithm, pivot rules typically switch multiple edges simultaneously and our lower bound for Dantzig's rule and the Largest Increase rule, which perform only single switches, seem novel. Regarding the simplex algorithm, the individual lower bounds were previously obtained separately via deformed hypercube constructions. In contrast to previous bounds for the simplex algorithm via Markov decision processes, our rigorous analysis is reasonably concise.

We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system $(V,\mathcal{F},\mathcal{B})$ with two families $\mathcal{F},\mathcal{B}$ of subsets of $V$. The task is to find a hitting set for $\mathcal{F}$ that minimizes the maximum number of elements in any of the sets of $\mathcal{B}$. Our focus is on determining the complexity of some special cases of Sparse-HS with respect to the sparseness $k$, which is the optimum number of hitting set elements in any set of $\mathcal{B}$. For the Sparse Vertex Cover (Sparse-VC) problem, $V$ is given by the vertex set of a graph, and $\mathcal{F}$ is its edge set. We prove NP-hardness for sparseness $k\geq 2$ and polynomial time solvability for $k=1$. We also provide a polynomial-time $2$-approximation for any $k$. A special case of Sparse-VC is Fair Vertex Cover (Fair-VC), where the family $\mathcal{B}$ is given by vertex neighbourhoods. For this problem we prove NP-hardness for constant $k$ and provide a polynomial-time $(2-\frac{1}{k})$-approximation. This is better than any approximation possible for Sparse-VC or Vertex Cover (under UGC). We then consider two problems derived from Sparse-HS related to the highway dimension, a graph parameter modelling transportation networks. Most algorithms for graphs of low highway dimension compute solutions to the $r$-Shortest Path Cover ($r$-SPC) problem, where $r>0$, $\mathcal{F}$ contains all shortest paths of length between $r$ and $2r$, and $\mathcal{B}$ contains all balls of radius $2r$. There is an XP algorithm that computes solutions to $r$-SPC of sparseness at most $h$ if the input graph has highway dimension $h$, but the existence if an FPT algorithm was open. We prove that $r$-SPC and also the related $r$-Highway Dimension ($r$-HD) problem are both W[1]-hard. Furthermore, we prove that $r$-SPC admits a polynomial-time $O(\log n)$-approximation.

We present a data structure that in a dynamic graph of treedepth at most d, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time , which matches the best known parameter dependency in the running time of a static fpt algorithm for computing the treedepth of a graph. This improves a result of Dvořák et al. [ESA 2014], who for the same problem achieved update time f(d) for some non-elementary (i.e. tower-exponential) function f. As a by-product, we improve known upper bounds on the sizes of minimal obstructions for having treedepth d from doubly-exponential in d to dO(d). As applications, we design new fully dynamic parameterized data structures for detecting long paths and cycles in general graphs. More precisely, for a fixed parameter k and a dynamic graph G, modified over time by edge insertions and deletions, our data structures maintain answers to the following queries: Does G contain a simple path on k vertices? Does G contain a simple cycle on at least k vertices? In the first case, the data structure achieves amortized update time . In the second case, the amortized update time is . In both cases we assume access to a dictionary on the edges of G.

We consider the online traveling salesperson problem (TSP), where requests appear online over time on the real line and need to be visited by a server initially located at the origin. We distinguish between closed and open online TSP, depending on whether the server eventually needs to return to the origin or not. While online TSP on the line is a very natural online problem that was introduced more than two decades ago, no tight competitive analysis was known to date. We settle this problem by providing tight bounds on the competitive ratios for both the closed and the open variant of the problem. In particular, for closed online TSP, we provide a 1.64-competitive algorithm, thus matching a known lower bound. For open online TSP, we give a new upper bound as well as a matching lower bound that establish the remarkable competitive ratio of 2.04. Additionally, we consider the online D IAL -A-R IDE problem on the line, where each request needs to be transported to a specified destination. We provide an improved non-preemptive lower bound of 1.75 for this setting, as well as an improved preemptive algorithm with competitive ratio 2.41. Finally, we generalize known and give new complexity results for the underlying offline problems. In particular, we give an algorithm with running time O ( n 2 ) for closed offline TSP on the line with release dates and show that both variants of offline D IAL -A-R IDE on the line are NP-hard for any capacity c ≥ 2 of the server.

The online Dial-a-Ride problem is a fundamental online problem in a metric space, where transportation requests appear over time and may be served in any order by a single server with unit speed. Restricted to the real line, online Dial-a-Ride captures natural problems like controlling a personal elevator. Tight results in terms of competitive ratios are known for the general setting and for online TSP on the line (where the source and target of each request coincide). In contrast, online Dial-a-Ride on the line has resisted tight analysis so far, even though it is a very natural online problem. We conduct a tight competitive analysis of the Smartstart algorithm that gave the best known results for the general, metric case. In particular, our analysis yields a new upper bound of 2.94 for open, nonpreemptive online Dial-a-Ride on the line, which improves the previous bound of 3.41 [S. O. Krumke, “Online Optimization Competitive Analysis and Beyond,” Habilitation thesis, Technische Universität Berlin, 2001]. The best known lower bound remains 2.04 [A. Bjelde et al., in Proceedings of the 28th Annual Symposium on Discrete Algorithms (SODA), SIAM, 2017, pp. 994--1005]. We also show that the known upper bound of 2 [N. Ascheuer, S. O. Krumke, and J. Rambau, in Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Springer, 2000, pp. 639--650] regarding Smartstart's competitive ratio for closed, nonpreemptive online Dial-a-Ride is tight on the line.

We consider the problem of collectively delivering some package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has limited energy which constrains the distance it can move. Hence multiple agents need to collaborate to move the package, each agent handing over the package to the next agent to carry it forward. Given the positions of the agents in the graph and their respective budgets, the problem of finding a feasible movement schedule for the agents can be challenging. We consider two variants of the problem: in non-returning delivery, the agents can stop anywhere; whereas in returning delivery, each agent needs to return to its starting location, a variant which has not been studied before. We first provide a polynomial-time algorithm for returning delivery on trees, which is in contrast to the known (weak) NP-hardness of the non-returning version. In addition, we give resource-augmented algorithms for returning delivery in general graphs. Finally, we give tight lower bounds on the required resource augmentation for both variants of the problem. In this sense, our results close the gap left by previous research.

We consider the open, non-preemptive online Dial-a-Ride problem on the real line, where transportation requests appear over time and need to be served by a single server. We give a lower bound of 2.0585 on the competitive ratio, which is the first bound that strictly separates online Dial-a-Ride on the line from online TSP on the line in terms of competitive analysis, and is the best currently known lower bound even for general metric spaces. On the other hand, we present an algorithm that improves the best known upper bound from 2.9377 to 2.6662. The analysis of our algorithm is tight.

We study the problem of deterministically exploring an undirected and initially unknown graph with n vertices either by a single agent equipped with a set of pebbles or by a set of collaborating agents. The vertices of the graph are unlabeled and cannot be distinguished by the agents, but the edges incident to a vertex have locally distinct labels. The graph is explored when all vertices have been visited by at least one agent. In this setting, it is known that for a single agent without pebbles Θ(log n ) bits of memory are necessary and sufficient to explore any graph with at most n vertices. We are interested in how the memory requirement decreases as the agent may mark vertices by dropping and retrieving distinguishable pebbles or when multiple agents jointly explore the graph. We give tight results for both questions showing that for a single agent with constant memory Θ(log log n ) pebbles are necessary and sufficient for exploration. We further prove that using collaborating agents instead of pebbles does not help as Θ(log log n ) agents with constant memory each are necessary and sufficient for exploration. For the upper bounds, we devise an algorithm for a single agent with constant memory that explores any n -vertex graph using O (log log n ) pebbles, even when n is not known a priori . The algorithm terminates after polynomial time and returns to the starting vertex. We further show that the algorithm can be realized with additional constant-memory agents rather than pebbles, implying that O (log log n ) agents with constant memory can explore any n -vertex graph. For the lower bound, we show that the number of agents needed for exploring any graph with at most n vertices is already Ω(log log n ) when we allow each agent to have at most O ((log n ) 1 -ε) bits of memory for any ε > 0. Our argument also implies that a single agent with sublogarithmic memory needs Θ(log log n ) pebbles to explore any n -vertex graph.

Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large networks/graphs. In this paper we propose and study a new framework contracting edges of a graph (merging vertices into supervertices) with the goal of preserving pairwise distances as accurately as possible. Formally, given an edge-weighted graph, the contraction should guarantee that for any two vertices at distance $d$, the corresponding supervertices remain at distance at least $\varphi(d)$ in the contracted graph, where $\varphi$ is a tolerance function bounding the permitted distance distortion. We present a comprehensive picture of the algorithmic complexity of the contraction problem for affine tolerance functions $\varphi(x)=x/\alpha-\beta$, where $\alpha\geq 1$ and $\beta\geq 0$ are arbitrary real-valued parameters. Specifically, we present polynomial-time algorithms for trees as well as hardness and inapproximability results for different graph classes, precisely separating easy and hard cases. Further we analyze the asymptotic behavior of contractions, and find efficient algorithms to compute (nonoptimal) contractions despite our hardness results.

We show that the Simplex Method, the Network Simplex Method—both with Dantzig’s original pivot rule—and the Successive Shortest Path Algorithm are NP-mighty . That is, each of these algorithms can be used to solve, with polynomial overhead, any problem in NP implicitly during the algorithm’s execution. This result casts a more favorable light on these algorithms’ exponential worst-case running times. Furthermore, as a consequence of our approach, we obtain several novel hardness results. For example, for a given input to the Simplex Algorithm, deciding whether a given variable ever enters the basis during the algorithm’s execution and determining the number of iterations needed are both NP-hard problems. Finally, we close a long-standing open problem in the area of network flows over time by showing that earliest arrival flows are NP-hard to obtain.

Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large networks/graphs. \nIn this paper we propose and study a new framework contracting edges of a graph (merging vertices into super-vertices) with the goal of preserving pairwise distances as accurately as possible. \nFormally, given an edge-weighted graph, the contraction should guarantee that for any two vertices at distance d, the corresponding super-vertices remain at distance at least \\varphi(d) in the contracted graph, where \\varphi is a tolerance function bounding the permitted distance distortion. \nWe present a comprehensive picture of the algorithmic complexity of the contraction problem for affine tolerance functions \\varphi(x)=x/\\alpha-\\beta, where \\alpha \\geq 1 and \\beta \\geq 0 are arbitrary real-valued parameters. \nSpecifically, we present polynomial-time algorithms for trees as well as hardness and inapproximability results for different graph classes, precisely separating easy and hard cases. \nFurther we analyze the asymptotic behavior of the size of contractions, and find efficient algorithms to compute (non-optimal) contractions despite our hardness results.

We consider the online traveling salesperson problem (TSP), where requests appear online over time on the real line and need to be visited by a server initially located at the origin. We distinguish between closed and open online TSP, depending on whether the server eventually needs to return to the origin or not. While online TSP on the line is a very natural online problem that was introduced more than two decades ago, no tight competitive analysis was known to date. We settle this problem by providing tight bounds on the competitive ratios for both the closed and the open variant of the problem. In particular, for closed online TSP, we provide a 1.64-competitive algorithm, thus matching a known lower bound. For open online TSP, we give a new upper bound as well as a matching lower bound that establish the remarkable competitive ratio of 2.04. Additionally, we consider the online Dial-A-Ride problem on the line, where each request needs to be transported to a specified destination. We provide an improved non-preemptive lower bound of 1.75 for this setting, as well as an improved preemptive algorithm with competitive ratio 2.41. Finally, we generalize known and give new complexity results for the underlying offline problems. In particular, we give an algorithm with running time O(n2) for closed offline TSP on the line with release dates and show that both variants of offline Dial-A-Ride on the line are NP-hard for any capacity c ≥ 2 of the server.

Binary search finds a given element in a sorted array with an optimal number of log n queries. However, binary search fails even when the array is only slightly disordered or access to its elements is subject to errors. We study the worst-case query complexity of search algorithms that are robust to imprecise queries and that adapt to perturbations of the order of the elements. We give (almost) tight results for various parameters that quantify query errors and that measure array disorder. In particular, we exhibit settings where query complexities of log n + ck, (1+epsilon) log n + ck, and sqrt(cnk)+o(nk) are best-possible for parameter value k, any epsilon > 0, and constant c.

We study the problem of packing a knapsack without knowing its capacity. Whenever we attempt to pack an item that does not fit, the item is discarded; if the item fits, we have to include it in the packing. We show that there is always a policy that packs a value within factor 2 of the optimum packing, irrespective of the actual capacity. If all items have unit density, we achieve a factor equal to the golden ratio $\varphi\approx1.618$. Both factors are shown to be best possible. In fact, we obtain the above factors using packing policies that are universal in the sense that they fix a particular order of the items in the beginning and try to pack the items in this order, without changing the order later on. We give efficient algorithms computing these policies. On the other hand, we show that, for any $\alpha>1$, the problem of deciding whether a given universal policy achieves a factor of $\alpha$ is ${\mathsf{coNP}}$-complete. If $\alpha$ is part of the input, the same problem is shown to be ${\mathsf{coNP}}$-complete for items with unit densities. Finally, we show that it is ${\mathsf{coNP}}$-hard to decide, for given $\alpha$, whether a set of items admits a universal policy with factor $\alpha$, even if all items have unit densities.

We consider the fundamental problem of exploring an undirected and initially unknown graph by an agent with little memory. The vertices of the graph are unlabeled, and the edges incident to a vertex have locally distinct labels. In this setting, it is known that ⊝(log n) bits of memory are necessary and sufficient to explore any graph with at most n vertices. We show that this memory requirement can be decreased significantly by making a part of the memory distributable in the form of pebbles. A pebble is a device that can be dropped to mark a vertex and can be collected when the agent returns to the vertex. We show that for an agent ℴ(log log n) distinguishable pebbles and bits of memory are sufficient to explore any bounded-degree graph with at most n vertices. We match this result with a lower bound exhibiting that for any agent with sub-logarithmic memory, Ω(log log n) distinguishable pebbles are necessary for exploration.

Circuit-augmentation algorithms are generalizations of the simplex method, where in each step one is allowed to move along a fixed set of directions, called circuits, that is a superset of the edges of a polytope. We show that in the circuit-augmentation framework the greatest-improvement and Dantzig pivot rules are NP-hard, already for 0/1-LPs. Differently, the steepest-descent pivot rule can be carried out in polynomial time in the 0/1 setting, and the number of circuit augmentations required to reach an optimal solution according to this rule is strongly polynomial for 0/1-LPs. The number of circuit augmentations has been of interest as a proxy for the number of steps in the simplex method, and the circuit-diameter of polyhedra has been studied as a lower bound to the combinatorial diameter of polyhedra. Extending prior results, we show that for any polyhedron $P$ the circuit-diameter is bounded by a polynomial in the input bit-size of $P$. This is in contrast with the best bounds for the combinatorial diameter of polyhedra. Interestingly, we show that the circuit-augmentation framework can be exploited to make novel conclusions about the classical simplex method itself: In particular, as a byproduct of our circuit results, we prove that (i) computing the shortest (monotone) path to an optimal solution on the 1-skeleton of a polytope is NP-hard, and hard to approximate within a factor better than 2, and (ii) for $0/1$ polytopes, a monotone path of strongly polynomial length can be constructed using steepest improving edges.

We consider the exploration of a simple polygon P by a robot that moves from vertex to vertex along edges of the visibility graph of P . The visibility graph has a vertex for every vertex of P and an edge between two vertices if they see each other—that is, if the line segment connecting them lies inside P entirely. While located at a vertex, the robot is capable of ordering the vertices it sees in counterclockwise order as they appear on the boundary, and for every two such vertices, it can distinguish whether the angle between them is convex (⩽ π) or reflex ( > π). Other than that, distant vertices are indistinguishable to the robot. We assume that an upper bound on the number of vertices is known. We obtain the general result that a robot exploring any locally oriented, arc-labeled graph G can always determine the base graph of G . Roughly speaking, this is the smallest graph that cannot be distinguished by a robot from G by its observations alone, no matter how it moves. Combining this result with various other techniques allows the ability to show that a robot exploring a polygon P with the preceding capabilities is always capable of reconstructing the visibility graph of P . We also show that multiple identical, indistinguishable, and deterministic robots of this kind can always solve the weak rendezvous problem in which they need to position themselves such that they mutually see each other—for instance, such that they form a clique in the visibility graph.

We study the problem of packing a knapsack without knowing its capacity. Whenever we attempt to pack an item that does not fit, the item is discarded; if the item fits, we have to include it in the packing. We show that there is always a policy that packs a value within factor 2 of the optimum packing, irrespective of the actual capacity. If all items have unit density, we achieve a factor equal to the golden ratio. Both factors are shown to be best possible. In fact, we obtain the above factors using packing policies that are universal in the sense that they fix a particular order of the items and try to pack the items in this order, independent of the observations made while packing. We give efficient algorithms computing these policies. On the other hand, we show that, for any a>1, the problem of deciding whether a given universal policy achieves a factor of a is coNP-complete. If a is part of the input, the same problem is shown to be coNP-complete for items with unit densities. Finally, we show that it is coNP-hard to decide, for given a, whether a set of items admits a universal policy with factor a, even if all items have unit densities.