Given a graph with edge costs and vertex profits and given a budget B, the Orienteering Problem asks for a walk of cost at most B of maximum profit. Additionally, each profit may be given with a time window within it can be collected by the walk. While the Orienteering Problem and thus the version with time windows are NP-hard in general, it remains open on numerous special graph classes. Since in several applications, especially for planning a route from A to B with waypoints, the input graph can be restricted to tree-like or path-like structures, in this paper we consider orienteering on these graph classes. While the Orienteering Problem with time windows is NP-hard even on undirected paths and cycles, and remains so even if all profits must be collected, we show that for directed paths it can be solved efficiently, even if each profit can be collected in one of several time windows. The same case is shown to be NP-hard for directed cycles. Particularly interesting is the Orienteering Problem on a directed cycle with one time window per profit. We give an efficient algorithm for the case where all time windows are shorter than the length of the cycle, resulting in a 2-approximation for the general setting. We further develop a polynomial-time approximation scheme for this problem and give a polynomial algorithm for the case where all profits must be collected. For the Orienteering Problem with time windows for the edges, we give a quadratic time algorithm for undirected paths and observe that the problem is NP-hard for trees. In the variant without time windows, we show that on trees and thus on graphs with bounded tree-width the Orienteering Problem remains NP-hard. We present, however, an FPT algorithm to solve orienteering with unit profits that we then use to obtain a ($1+\varepsilon$)-approximation algorithm on graphs with arbitrary profits and bounded tree-width.
Whitehead doubles provide a plethora of examples of knots that are topologically slice but not smoothly slice. We discuss the problem of the Whitehead double of the Figure 8 knot and survey commonly used techniques to obstructing sliceness. Additionally, we improve bounds in general for the non-orientable 4 genus of $t$-twisted Whitehead doubles and provide genus 1 non-orientable cobordisms to cable knots.
The need for statistical models of orientations arises in many applications in engineering and computer science. Orientational data appear as sets of angles, unit vectors, rotation matrices or quaternions. In the field of directional statistics, a lot of advances have been made in modelling such types of data. However, only a few of these tools are used in engineering and computer science applications. Hence, this paper aims to serve as a cheat sheet for those probability distributions of orientations. Models for 1-DOF, 2-DOF and 3-DOF orientations are discussed. For each of them, expressions for the density function, fitting to data, and sampling are presented. The paper is written with a compromise between engineering and statistics in terms of notation and terminology. A Python library with functions for some of these models is provided. Using this library, two examples of applications to real data are presented.
The dichromatic number of a digraph is the minimum size of a partition of its vertices into acyclic induced subgraphs. Given a class of digraphs $\mathcal C$, a digraph $H$ is a hero in $\mc C$ if $H$-free digraphs of $\mathcal C$ have bounded dichromatic number. In a seminal paper, Berger at al. give a simple characterization of all heroes in tournaments. In this paper, we give a simple proof that heroes in quasi-transitive oriented graphs are the same as heroes in tournaments. We also prove that it is not the case in the class of oriented multipartite graphs, disproving a conjecture of Aboulker, Charbit and Naserasr. We also give a full characterisation of heroes in oriented complete multipartite graphs up to the status of a single tournament on $6$ vertices.
An oriented circulant graph is called integral if all eigenvalues of its Hermitian adjacency matrix are integers. The main purpose of this paper is to investigate the existence of perfect state transfer ($\PST$ for short) and multiple state transfer ($\MST$ for short) on integral oriented circulant graphs. Specifically, a characterization of $\PST$ (or $\MST$) on integral oriented circulant graphs is provided. As an application, we also obtain a closed-form expression for the number of integral oriented circulant graphs with fixed order having $\PST$ (or $\MST$).
Let $G$ be a connected graph and let $T$ be a spanning tree of $G$. A partial orientation $σ$ of $G$ respect to $T$ is an orientation of the edges of $G$ except those edges of $T$, the resulting graph associated with which is denoted by $G_T^σ$. In this paper we prove that there exists a partial orientation $σ$ of $G$ respect to $T$ such that the largest eigenvalue of the Hermitian adjacency matrix of $G_T^σ$ is at most the largest absolute value of the roots of the matching polynomial of $G$.
It is well known that \textit{every} Eulerian orientation of an Eulerian $2k$-edge connected (undirected) graph is strongly $k$-edge connected. An important goal in the area is to obtain analogous results for other types of connectivity, such as node connectivity and element connectivity. We show that \textit{every} Eulerian orientation of the hypercube of degree $2k$ is strongly $k$-node connected.
Patricia R. Barbosa, Yugandhar Sarkale, Edwin K. P. Chong
et al.
We investigate the challenging problem of integrating detection, signal processing, target tracking, and adaptive waveform scheduling with lookahead in urban terrain. We propose a closed-loop active sensing system to address this problem by exploiting three distinct levels of diversity: (1) spatial diversity through the use of coordinated multistatic radars; (2) waveform diversity by adaptively scheduling the transmitted waveform; and (3) motion model diversity by using a bank of parallel filters matched to different motion models. Specifically, at every radar scan, the waveform that yields the minimum trace of the one-step-ahead error covariance matrix is transmitted; the received signal goes through a matched-filter, and curve fitting is used to extract range and range-rate measurements that feed the LMIPDA-VSIMM algorithm for data association and filtering. Monte Carlo simulations demonstrate the effectiveness of the proposed system in an urban scenario contaminated by dense and uneven clutter, strong multipath, and limited line-of-sight.
Siddharth Karamcheti, Edward C. Williams, Dilip Arumugam
et al.
Robots operating alongside humans in diverse, stochastic environments must be able to accurately interpret natural language commands. These instructions often fall into one of two categories: those that specify a goal condition or target state, and those that specify explicit actions, or how to perform a given task. Recent approaches have used reward functions as a semantic representation of goal-based commands, which allows for the use of a state-of-the-art planner to find a policy for the given task. However, these reward functions cannot be directly used to represent action-oriented commands. We introduce a new hybrid approach, the Deep Recurrent Action-Goal Grounding Network (DRAGGN), for task grounding and execution that handles natural language from either category as input, and generalizes to unseen environments. Our robot-simulation results demonstrate that a system successfully interpreting both goal-oriented and action-oriented task specifications brings us closer to robust natural language understanding for human-robot interaction.
We consider the holographic computation of two dimensional conformal field theory partition functions on non-orientable surfaces. We classify the three dimensional geometries that give bulk saddle point contributions to the partition function, and find that there are fewer saddles than in the orientable case. For example, for the Klein bottle there is a single smooth saddle and a single additional saddle with an orbifold singularity. We argue that one must generally include singular bulk saddle points in order to reproduce the CFT results. We also discuss loop corrections to these partition functions for the Klein bottle.
In the present paper, we consider several valid notions of orientability of Alexandov spaces and prove that all such conditions are equivalent. Further, we give topological and geometric applications of the orientability. In particular, a Poincaré-type duality theorem is proved. As a corollary to the duality theorem, we also prove that if a closed Alexandrov space admits a positive curvature bound in a synthetic sense, then its codimension one homology vanishes. Further, we obtain a filling radius inequality for closed orientable Alexandrov spaces.
Persistent homology provides a new approach for the topological simplification of big data via measuring the life time of intrinsic topological features in a filtration process and has found its success in scientific and engineering applications. However, such a success is essentially limited to qualitative data characterization, identification and analysis (CIA). In this work, we outline a general protocol to construct objective-oriented persistent homology methods. The minimization of the objective functional leads to a Laplace-Beltrami operator which generates a multiscale representation of the initial data and offers an objective oriented filtration process. The resulting differential geometry based objective-oriented persistent homology is able to preserve desirable geometric features in the evolutionary filtration and enhances the corresponding topological persistence. The consistence between Laplace-Beltrami flow based filtration and Euclidean distance based filtration is confirmed on the Vietoris-Rips complex for a large amount of numerical tests. The convergence and reliability of the present Laplace-Beltrami flow based cubical complex filtration approach are analyzed over various spatial and temporal mesh sizes. The efficiency and robustness of the present method are verified by more than 500 fullerene molecules. It is shown that the proposed persistent homology based quantitative model offers good predictions of total curvature energies for ten types of fullerene isomers. The present work offers the first example to design objective-oriented persistent homology to enhance or preserve desirable features in the original data during the filtration process and then automatically detect or extract the corresponding topological traits from the data.
Under mean radius of curvature flow, a closed convex surface in Euclidean space is known to expand exponentially to infinity. In the 3-dimensional case we prove that the oriented normals to the flowing surface converge to the oriented normals of a round sphere whose centre is determined by the initial surface. To prove this we show that the oriented normal lines, considered as a surface in the space of all oriented lines, evolve by a parabolic flow which preserves the Lagrangian condition. Moreover, this flow converges to a holomorphic Lagrangian section, which form the set of oriented lines through a point. The coordinates of this centre point are projections of the support function into the first non-zero eigenspace of the spherical Laplacian and are given by explicit integrals of initial surface data.
Harry Kesten, Vladas Sidoravicius, Maria Eulalia Vares
On the lattice $\widetilde{\mathbb Z}^2_+:={(x,y)\in \mathbb Z \times \mathbb Z_+\colon x+y \text{is even}}$ we consider the following oriented (northwest-northeast) site percolation: the lines $H_i:={(x,y)\in \widetilde {\mathbb Z}^2_+ \colon y=i}$ are first declared to be bad or good with probabilities $\de$ and $1-\de$ respectively, independently of each other. Given the configuration of lines, sites on good lines are open with probability $p_{_G}>p_c$, the critical probability for the standard oriented site percolation on $\mathbb Z_+ \times \mathbb Z_+$, and sites on bad lines are open with probability $p_{_B}$, some small positive number, independently of each other. We show that given any pair $p_{_G}>p_c$ and $p_{_B}>0$, there exists a $δ(p_{_G}, p_{_B})>0$ small enough, so that for $δ\le δ(p_G,p_B)$ there is a strictly positive probability of oriented percolation to infinity from the origin.
We give an explicit formula for the holonomy of the orientation bundle of a family of real Cauchy-Riemann operators. A special case of this formula resolves the orientability question for spaces of maps from Riemann surfaces with Lagrangian boundary condition. As a corollary, we show that the local system of orientations on the moduli space of J-holomorphic maps from a bordered Riemann surface to a symplectic manifold is isomorphic to the pull-back of a local system defined on the product of the Lagrangian and its free loop space. As another corollary, we show that certain natural bundles over these moduli spaces have the same local systems of orientations as the moduli spaces themselves (this is a prerequisite for integrating the Euler classes of these bundles). We will apply these conclusions in future papers to construct and compute open Gromov-Witten invariants in a number of settings.
A unicellular map is the embedding of a connected graph in a surface in such a way that the complement of the graph is a topological disk. In this paper we present a bijective link between unicellular maps on a non-orientable surface and unicellular maps of a lower topological type, with distinguished vertices. From that we obtain a recurrence equation that leads to (new) explicit counting formulas for non-orientable unicellular maps of fixed topology. In particular, we give exact formulas for the precubic case (all vertices of degree 1 or 3), and asymptotic formulas for the general case, when the number of edges goes to infinity. Our strategy is inspired by recent results obtained by the second author for the orientable case, but significant novelties are introduced: in particular we construct an involution which, in some sense, "averages" the effects of non-orientability.
It is shown that nonsymmetric microobjects orient while settling under gravity in a viscous fluid. To analyze this process, a simple shape is chosen: a non-deformable `chain'. The chain consists of two straight arms, made of touching solid spheres. In the absence of external torques, the spheres are free to spin along the arms. The motion of the chain is evaluated by solving the Stokes equations with the use of the multipole method. It is demonstrated that the spinning beads speed up sedimentation by a small amount, and increase the orientation rate significantly in comparison to the corresponding rigid chain. It is shown that chains orient towards the V-shaped stable stationary configuration. In contrast, rods and star-shaped microobjects do not rotate. The hydrodynamic orienting is relevant for efficient swimming of non-symmetric microobjects, and for sedimenting suspensions.