More Like this

1. Graph Exploration by Energy-Sharing Mobile Agents

   Czyzowicz, J. ; Dobrev, S. ; Killick, R. ; Kranakis, E. ; Krizanc, D. ; Narayanan, L. ; Opatrny, J ; Pankratov, D. ; Shende, S. ( July 2021 , 28th International Colloquium on Structural Information and Communication Complexity (SIROCCO))

   null (Ed.)

   We consider the problem of collective exploration of a known n- node edge-weighted graph by k mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbitrary subset of nodes in the graph, and each agent has an initial, possibly different, amount of energy. The goal of the exploration problem is for every edge in the graph to be traversed by at least one agent. The amount of energy used by an agent to travel distance x is proportional to x. In our model, the agents can share energy when co-located: when two agents meet, one can transfer part of its energy to the other. For an n-node path, we give an O(n+k) time algorithm that either nds an exploration strategy, or reports that one does not exist. For an n-node tree with l leaves, we give an O(n+lk^2) algorithm that finds an exploration strategy if one exists. Finally, for the general graph case, we show that the problem of deciding if exploration is possible by energy-sharing agents is NP-hard, even for 3-regular graphs. In addition, we show that it is always possible to find an exploration strategy if the total energy of the agents is at least twice the total weight of the edges; moreover, this is asymptotically optimal. 

   more » « less
2. Hardness of Approximation for Orienteering with Multiple Time Windows

   Garg, Naveen ; Khanna, Sanjeev ; Kumar, Amit ( January 2021 , Proceedings of the ACM-SIAM Symposium on Discrete Algorithms)

   null (Ed.)

   Vehicle routing problems are a broad class of combinatorial optimization problems that can be formulated as the problem of finding a tour in a weighted graph that optimizes some function of the visited vertices. For instance, a canonical and extensively studied vehicle routing problem is the orienteering problem where the goal is to find a tour that maximizes the number of vertices visited by a given deadline. In this paper, we consider the computational tractability of a well-known generalization of the orienteering problem called the Orient-MTW problem. The input to Orient-MTW consists of a weighted graph G(V, E) where for each vertex v ∊ V we are given a set of time instants Tv ⊆ [T], and a source vertex s. A tour starting at s is said to visit a vertex v if it transits through v at any time in the set Tv. The goal is to find a tour starting at the source vertex that maximizes the number of vertices visited. It is known that this problem admits a quasi-polynomial time O(log OPT)-approximation ratio where OPT is the optimal solution value but until now no hardness better than an APX-hardness was known for this problem. Our main result is an -hardness for this problem that holds even when the underlying graph G is an undirected tree. This is the first super-constant hardness result for the Orient-MTW problem. The starting point for our result is the hardness of the SetCover problem which is known to hold on instances with a special structure. We exploit this special structure of the hard SetCover instances to first obtain a new proof of the APX-hardness result for Orient-MTW that holds even on trees of depth 2. We then recursively amplify this constant factor hardness to an -hardness, while keeping the resulting topology to be a tree. Our amplified hardness proof crucially utilizes a delicate concavity property which shows that in our encoding of SetCover instances as instances of the Orient-MTW problem, whenever the optimal cost for SetCover instance is large, any tour, no matter how it allocates its time across different sub-trees, can not visit too many vertices overall. We believe that this reduction template may also prove useful in showing hardness of other vehicle routing problems. 

   more » « less
3. Planning High-Level Paths in Hostile, Dynamic, and Uncertain Environments

   https://doi.org/10.1613/jair.1.12077  

   Banfi, Jacopo ; Shree, Vikram ; Campbell, Mark ( September 2020 , Journal of Artificial Intelligence Research)

   null (Ed.)

   This paper introduces and studies a graph-based variant of the path planning problem arising in hostile environments. We consider a setting where an agent (e.g. a robot) must reach a given destination while avoiding being intercepted by probabilistic entities which exist in the graph with a given probability and move according to a probabilistic motion pattern known a priori. Given a goal vertex and a deadline to reach it, the agent must compute the path to the goal that maximizes its chances of survival. We study the computational complexity of the problem, and present two algorithms for computing high quality solutions in the general case: an exact algorithm based on Mixed-Integer Nonlinear Programming, working well in instances of moderate size, and a pseudo-polynomial time heuristic algorithm allowing to solve large scale problems in reasonable time. We also consider the two limit cases where the agent can survive with probability 0 or 1, and provide specialized algorithms to detect these kinds of situations more efficiently. 

   more » « less
4. Graphs with Tunable Chromatic Numbers for Parallel Coloring

   https://doi.org/10.1137/1.9781611976229.6  

   Cheng, Xin ; Maji, Hemanta ; Pothen, Alex ( January 2020 , SIAM 2020 Workshop on Combinatorial Scientific Computing)

   We consider how to generate graphs of arbitrary size whose chromatic numbers can be chosen (or are well-bounded) for testing graph coloring algorithms on parallel computers. For the distance-1 graph coloring problem, we identify three classes of graphs with this property. The first is the Erdős-Rényi random graph with prescribed expected degree, where the chromatic number is known with high probability. It is also known that the Greedy algorithm colors this graph using at most twice the number of colors as the chromatic number. The second is a random geometric graph embedded in hyperbolic space where the size of the maximum clique provides a tight lower bound on the chromatic number. The third is a deterministic graph described by Mycielski, where the graph is recursively constructed such that its chromatic number is known and increases with graph size, although the size of the maximum clique remains two. For Jacobian estimation, we bound the distance-2 chromatic number of random bipartite graphs by considering its equivalence to distance-1 coloring of an intersection graph. We use a “balls and bins” probabilistic analysis to establish a lower bound and an upper bound on the distance-2 chromatic number. The regimes of graph sizes and probabilities that we consider are chosen to suit the Jacobian estimation problem, where the number of columns and rows are asymptotically nearly equal, and have number of nonzeros linearly related to the number of columns. Computationally we verify the theoretical predictions and show that the graphs are often be colored optimally by the serial and parallel Greedy algorithms. 

   more » « less
5. Enhanced multi-objective A* using balanced binary search trees

   Ren, Zhongqiang ; Zhan, Richard ; Sivakumar, Rathinam ; Likhachev, Maxim ; Choset, Howie ( January 2022 , Proceedings of the International Symposium on Combinatorial Search)

   NA (Ed.)

   This work addresses a Multi-Objective Shortest Path Problem (MO-SPP) on a graph where the goal is to find a set of Pareto-optimal solutions from a start node to a destination in the graph. A family of approaches based on MOA* have been developed to solve MO-SPP in the literature. Typically, these approaches maintain a “frontier” set at each node during the search process to keep track of the non-dominated, partial paths to reach that node. This search process becomes computationally expensive when the number of objectives increases as the number of Pareto-optimal solutions becomes large. In this work, we introduce a new method to efficiently maintain these frontiers for multiple objectives by incrementally constructing balanced binary search trees within the MOA* search framework. We first show that our approach correctly finds the Pareto-optimal front, and then provide extensive simulation results for problems with three, four and five objectives to show that our method runs faster than existing techniques by up to an order of magnitude. 

   more » « less