We study the problem of deterministically exploring an undirected and initially unknown graph with n vertices either by a single agent equipped set pebbles or collaborating agents. The are unlabeled cannot be distinguished agents, but edges incident to vertex have locally distinct labels. is explored when all been visited at least one agent. In this setting, it known that for without Θ(log ) bits memory necessary sufficient explore any most vertices. interested in how requirement decreases...

We consider the problem of delivering $m$ messages between specified source-target pairs in a weighted undirected graph, by $k$ mobile agents initially located at distinct nodes graph. Each agent consumes energy proportional to distance it travels graph and we are interested optimizing total consumption for team agents. Unlike previous related work, heterogeneous with different rates (weights~$w_i$). To solve delivery problem, face three major challenges: \emph{Collaboration} (how work...

We present a detailed investigation of minimum detection efficiencies, below which local realism cannot be violated by any quantum system dimension in bipartite Bell experiments. Lower bounds on these efficiencies are determined with the help linear programming techniques. Our approach is based observation that possible correlation originating from state an arbitrary dimensional Hilbert space sandwiched between two probability polytopes, namely (Bell) polytope and corresponding nonlocal...

Abstract We study a Markovian agent-based model (MABM) in this paper. Each agent is endowed with local state that changes over time as the interacts its neighbours. The neighbourhood structure given by graph. Recently, Simon, Taylor, and Kiss [40] used automorphisms of underlying graph to generate lumpable partition joint space, ensuring Markovianness lumped process for binary dynamics. However, many large random graphs tend become asymmetric, rendering automorphism-based lumping approach...

Abstract The question whether the Simplex Algorithm admits an efficient pivot rule remains one of most important open questions in discrete optimization. While many natural, deterministic rules are known to yield exponential running times, random-facet was shown have a subexponential time. For long time, Zadeh’s remained prominent candidate for first with We present lower bound construction that shows is fact worst case. Our based on close relation Strategy Improvement Parity Games and...

We consider the online traveling salesperson problem (TSP), where requests appear over time on real line and need to be visited by a server initially located at origin. distinguish between closed open TSP, depending whether eventually needs return origin or not. While TSP is very natural that was introduced more than two decades ago, no tight competitive analysis known date. settle this providing bounds ratios for both variant of problem. In particular, we provide 1.64-competitive algorithm,...

We consider the exploration of a simple polygon P by robot that moves from vertex to along edges visibility graph . The has for every and an edge between two vertices if they see each other—that is, line segment connecting them lies inside entirely. While located at vertex, is capable ordering it sees in counterclockwise order as appear on boundary, such vertices, can distinguish whether angle convex (⩽ π) or reflex ( > π). Other than that, distant are indistinguishable robot. assume...

We study the problem of packing a knapsack without knowing its capacity. Whenever we attempt to pack an item that does not fit, is discarded; if fits, have include it in packing. show there always policy packs value within factor 2 optimum packing, irrespective actual If all items unit density, achieve equal golden ratio $\varphi\approx1.618$. Both factors are shown be best possible. In fact, obtain above using policies universal sense they fix particular order beginning and try this order,...

We propose to classify the power of algorithms by complexity problems that they can be used solve. Instead restricting problem a particular algorithm was designed solve explicitly, however, we include that, with polynomial overhead, solved 'implicitly' during algorithm's execution. For example, allow decision suitably transforming input, executing algorithm, and observing whether specific bit in its internal configuration ever switches execution.We show Simplex Method, Network Method (both...

We consider the online traveling salesperson problem (TSP), where requests appear over time on real line and need to be visited by a server initially located at origin. distinguish between closed open TSP, depending whether eventually needs return origin or not. While TSP is very natural that was introduced more than two decades ago, no tight competitive analysis known date. settle this providing bounds ratios for both variant of problem. In particular, we provide 1.64-competitive algorithm,...

We show that the Simplex Method, Network Method—both with Dantzig’s original pivot rule—and Successive Shortest Path Algorithm are NP-mighty . That is, each of these algorithms can be used to solve, polynomial overhead, any problem in NP implicitly during algorithm’s execution. This result casts a more favorable light on algorithms’ exponential worst-case running times. Furthermore, as consequence our approach, we obtain several novel hardness results. For example, for given input Algorithm,...

We propose to classify the power of algorithms by complexity problems that they can be used solve. Instead restricting problem a particular algorithm was designed solve explicitly, however, we include that, with polynomial overhead, solved ‘implicitly’ during algorithm's execution. For example, allow decision suitably transforming input, executing algorithm, and observing whether specific bit in its internal configuration ever switches execution.We show Simplex Method, Network Method (both...