搜索结果：Ford

The dawning of the Space Age marked the start of an ongoing relationship between the professional astronomical community and both state and non-state actors that launch and operate spacecraft in near-Earth orbital space. While the Cold War heated up in the late 1950s, military uses of outer space quickly came into conflict with the priorities of astronomers then building ever-bigger ground-based telescopes and envisioning the first generation of space telescopes. As the threat of global thermonuclear war loomed, the United States carried out Project West Ford, which tested an 'artificial ionosphere' for microwave radio propagation by placing several hundred million tiny copper dipoles into a belt orbiting the Earth. While the test was ultimately successful, it ignited a firestorm of concern and criticism among astronomers and ultimately influenced the framing of the United Nations Outer Space Treaty. Here we examine the history of Project West Ford as it prompted astronomers to react, comparing it with the ongoing problem of the potential impact of large satellite constellations on astronomical research.

The contributions of this short technical note are two-fold. Firstly, we introduce a modified version of a generalized Bellman-Ford algorithm calculating the value function of optimal control problems defined on hyper-graphs. Those Bellman-Ford algorithms can be used in particular for the synthesis of near-optimal controllers by the principle of symbolic control. Our modification causes less nodes of the hyper-graph being iterated during the execution compared to our initial version of the algorithm published in 2020. Our second contribution lies in the field of Plan recognition applied to drone missions driven by symbolic controllers. We address and resolve the Plan and Goal Recognition monitor's dependence on a pre-defined initial guess for a drone's task allocation and mission execution. To validate the enhanced implementation, we use a more challenging scenario for UAV-based aerial firefighting, demonstrating the practical applicability and robustness of the system architecture.

We investigate a particular choice of the Ford fundamental domain of the congruence subgroup $Γ_0(N)$ and define a notion of complexity $c(N)$ accordingly, which is a nonnegative integer and carries some information on the shape of the Ford domain. The property that $c(N)=0$ first appeared as a technical assumption in a paper by Pohl, which is closely related to a conjecture of Zagier on the "reduction theory" of $Γ_0(N)$. In this paper, we give a complete classification of positive integers $N$ with $c(N)=0$, and we also show that $c(N)$ goes to infinity if both the number of distinct prime factors of $N$ and the smallest prime factor of $N$ go to infinity.

A classical algorithm by Bellman and Ford from the 1950's computes shortest paths in weighted graphs on $n$ vertices and $m$ edges with possibly negative weights in $O(mn)$ time. Indeed, this algorithm is taught regularly in undergraduate Algorithms courses. In 2023, after nearly 70 years, Fineman \cite{fineman2024single} developed an $\tilde{O}(m n^{8/9})$ expected time algorithm for this problem. Huang, Jin and Quanrud improved on Fineman's startling breakthrough by providing an $\tilde{O}(m n^{4/5} )$ time algorithm. This paper builds on ideas from those results to produce an $\tilde{O}(m\sqrt{n})$ expected time algorithm. The simple observation that distances can be updated with respect to the reduced costs for a price function in linear time is key to the improvement. This almost immediately improves the previous work. To produce the final bound, this paper provides recursive versions of Fineman's structures.

The Bellman-Ford algorithm for single-source shortest paths repeatedly updates tentative distances in an operation called relaxing an edge. In several important applications a non-adaptive (oblivious) implementation is preferred, which means fixing the entire sequence of relaxations upfront, independently of the edge-weights. Such an implementation performs, in a dense graph on $n$ vertices, $(1 + o(1))n^3$ relaxations. An improvement by Yen from 1970 reduces the number of relaxations by a factor of two. We show that no further constant-factor improvements are possible, and every non-adaptive deterministic algorithm based on relaxations must perform $(\frac{1}{2} - o(1))n^3$ steps. This improves an earlier lower bound of Eppstein of $(\frac{1}{6} - o(1))n^3$. Given that a non-adaptive randomized variant of Bellman-Ford with at most $(\frac{1}{3} + o(1))n^3$ relaxations (with high probability) is known, our result implies a strict separation between deterministic and randomized strategies, answering an open question of Eppstein. On the complexity side, we show that deciding whether a given relaxation sequence is guaranteed to yield correct distances is NP-hard, even with the complet

Consider a finite directed graph without cycles in which the arrows are weighted. We present an algorithm for the computation of a new distance, called path-length-weighted distance, which has proven useful for graph analysis in the context of fraud detection. The idea is that the new distance explicitly takes into account the size of the paths in the calculations. Thus, although our algorithm is based on arguments similar to those at work for the Bellman-Ford and Dijkstra methods, it is in fact essentially different. We lay out the appropriate framework for its computation, showing the constraints and requirements for its use, along with some illustrative examples.

In this paper we give a single-source shortest-path algorithm that breaks, after over 65 years, the $O(n \cdot m)$ bound for the running time of the Bellman-Ford-Moore algorithm, where $n$ is the number of vertices and $m$ is the number of arcs of the graph. Our algorithm converts the input graph to a graph with nonnegative weights by performing at most $\min(2 \cdot \sqrt{n},2 \cdot \sqrt{m/\log n})$ calls to a modified version of Dijkstra's algorithm, such that the shortest-path trees are the same for the new graph as those for the original. When Dijkstra's algorithm is implemented using Fibonacci heaps, the running time of our algorithm is therefore $O(\sqrt{n} \cdot m + n \cdot \sqrt{m \log n})$.

Recent work has shown that leveraging learned predictions can improve the running time of algorithms for bipartite matching and similar combinatorial problems. In this work, we build on this idea to improve the performance of the widely used Ford-Fulkerson algorithm for computing maximum flows by seeding Ford-Fulkerson with predicted flows. Our proposed method offers strong theoretical performance in terms of the quality of the prediction. We then consider image segmentation, a common use-case of flows in computer vision, and complement our theoretical analysis with strong empirical results.

We study fractions associated to Ford circles which are extracted by means continuous curves. We show that the extracted fractions have similar properties to Farey sequences, like the Farey sum, and we prove that every ordered sequence that satisfies the Farey sum and has two adjacent fractions, can be extracted from Ford circles through continuous curves. This allows us to relate sequences of fractions that satisfy the Farey sum and continuous curves. We focus on the fractions $F_{1/m}$ extracted from inclined lines with positive slopes of the form $1/m$ and define jumps as the cardinality increments of these fractions with respect to $m$. We relate the expression for every jump to the prime omega function in terms of $m$ and find a cardinality formula related to the Möbius function, which we approximate with three tractable expressions that grow in a log-linear way considering estimations of sums related to Euler's totient function or the graph of the lattice points corresponding to the fractions $p/q$.

We initiate the study of deformations of groups in three-dimensional complex hyperbolic geometry. Let $$G=\left\langle ι_1, ι_2, ι_3, ι_4 \Bigg| \begin{array}{c} ι_1^2= ι_2^2 = ι_3^2=ι_4^2=id,\\ (ι_1 ι_3)^{2}=(ι_1 ι_4)^{3}=(ι_2 ι_4)^{2}=id \end{array}\right\rangle$$ be an abstract group. We study representations $ρ: G \rightarrow \mathbf{PU}(3,1)$, where $ρ( ι_{i})=I_{i}$ is a complex reflection fixing a complex hyperbolic plane in ${\bf H}^{3}_{\mathbb C}$ for $1 \leq i \leq 4$, with the additional condition that $I_1I_2$ is parabolic. When we assume two pairs of hyper-parallel complex hyperbolic planes have the same distance, then the moduli space $\mathcal{M}$ is parameterized by $(h,t) \in [1, \infty) \times [0, π]$ but $t \leq \operatorname{arccos}(-\frac{3h^2+1}{4h^2})$. In particular, $t=0$ and $t=\operatorname{arccos}(-\frac{3h^2+1}{4h^2})$ degenerate to ${\bf H}^{3}_{\mathbb R}$-geometry and ${\bf H}^{2}_{\mathbb C}$-geometry respectively. Using the Ford domain of $ρ_{(\sqrt{2},\operatorname{arccos}(-\frac{7}{8}))}(G)$ as a guide, we show $ρ_{(h,t)}$ is a discrete and faithful representation of $G \rightarrow \mathbf{PU}(3,1)$ when $(h,t) \in \mathcal{M}$ is near to $(\sqr

Link prediction is a very fundamental task on graphs. Inspired by traditional path-based methods, in this paper we propose a general and flexible representation learning framework based on paths for link prediction. Specifically, we define the representation of a pair of nodes as the generalized sum of all path representations, with each path representation as the generalized product of the edge representations in the path. Motivated by the Bellman-Ford algorithm for solving the shortest path problem, we show that the proposed path formulation can be efficiently solved by the generalized Bellman-Ford algorithm. To further improve the capacity of the path formulation, we propose the Neural Bellman-Ford Network (NBFNet), a general graph neural network framework that solves the path formulation with learned operators in the generalized Bellman-Ford algorithm. The NBFNet parameterizes the generalized Bellman-Ford algorithm with 3 neural components, namely INDICATOR, MESSAGE and AGGREGATE functions, which corresponds to the boundary condition, multiplication operator, and summation operator respectively. The NBFNet is very general, covers many traditional path-based methods, and can be

The Uhlenbeck-Ford (UF) model was originally proposed for the theoretical study of imperfect gases, given that all its virial coefficients can be evaluated exactly, in principle. Here, in addition to computing the previously unknown coefficients B11 through B13, we assess its applicability as a reference system in fluid-phase free-energy calculations using molecular simulation techniques. Our results demonstrate that, although the UF model itself is too soft, appropriately scaled Uhlenbeck- Ford (sUF) models provide robust reference systems that allow accurate fluid-phase free-energy calculations without the need for an intermediate reference model. Indeed, in addition to the accuracy with which their free energies are known and their convenient scaling properties, the fluid is the only thermodynamically stable phase for a wide range of sUF models. This set of favorable properties may potentially put the sUF fluid-phase reference systems on par with the standard role that harmonic and Einstein solids play as reference systems for solid-phase free-energy calculations.

This paper is about the problem of finding a shortest $s$-$t$ path using at most $h$ edges in edge-weighted graphs. The Bellman--Ford algorithm solves this problem in $O(hm)$ time, where $m$ is the number of edges. We show that this running time is optimal, up to subpolynomial factors, under popular fine-grained complexity assumptions. More specifically, we show that under the APSP Hypothesis the problem cannot be solved faster already in undirected graphs with non-negative edge weights. This lower bound holds even restricted to graphs of arbitrary density and for arbitrary $h \in O(\sqrt{m})$. Moreover, under a stronger assumption, namely the Min-Plus Convolution Hypothesis, we can eliminate the restriction $h \in O(\sqrt{m})$. In other words, the $O(hm)$ bound is tight for the entire space of parameters $h$, $m$, and $n$, where $n$ is the number of nodes. Our lower bounds can be contrasted with the recent near-linear time algorithm for the negative-weight Single-Source Shortest Paths problem, which is the textbook application of the Bellman--Ford algorithm.

It is well-known that the Ford-Fulkerson algorithm for finding a maximum flow in a network need not terminate if we allow the arc capacities to take irrational values. Every non-terminating example converges to a limit flow, but this limit flow need not be a maximum flow. Hence, one may pass to the limit and begin the algorithm again. In this way, we may view the Ford-Fulkerson algorithm as a transfinite algorithm. We analyze the transfinite running-time of the Ford-Fulkerson algorithm using ordinal numbers, and prove that the worst case running-time is $ω^{Θ(|E|)}$. For the lower bound, we show that we can model the Euclidean algorithm via Ford-Fulkerson on an auxiliary network. By running this example on a pair of incommensurable numbers, we obtain a new robust non-terminating example. We then describe how to glue $k$ copies of our Euclidean example in parallel to obtain running-time $ω^k$. An upper bound of $ω^{|E|}$ is established via induction on $|E|$. We conclude by illustrating a close connection to transfinite chip-firing as previously investigated by the first author.

We study the FeH Wing-Ford band at 9850 - 10200 Angstrons by means of the fit of synthetic spectra to the observations of M stars, employing recent model atmospheres. On the basis of the spectrum synthesis, we analyze the dependence of the band upon atmospheric parameters. FeH lines are a very sensitive surface gravity indicator, being stronger in dwarfs. They are also sensitive to metallicity (Allard & Hauschildt 1995). The blending with CN lines, which are stronger in giants, does not affect the response of the Wing-Ford band to surface gravity at low resolution (or high velocity dispersions) because CN lines, which are spread all along the spectrum, are smeared out at convolutions of FWHM $\simgreat$ 3 Angstrons. We conclude that the Wing-Ford band is a suitable dwarf/giant indicator for the study of composite stellar populations.

The Uhlenbeck-Ford model for soft repulsion, which has only a repulsive interaction, is extended by inclusion of an attraction. This extension still allows an analytical evaluation of the virial coefficients. The integrals over the graph contributions are reduced to a combinatorial problem. We have calculated the virial coefficients to order 6 in the density. A link is made between this model and more common interactions, like the 12-6 Lennard-Jones potential.

Study the general single-source shortest path problem. Firstly, define a path function on a set of some path with same source on a graph, and develop a kind of general single-source shortest path problem (GSSSP) on the defined path function. Secondly, following respectively the approaches of the well known Dijkstra's algorithm and Moore-Bellman-Ford algorithm, design an extended Dijkstra's algorithm (EDA) and an extended Moore-Bellman-Ford algorithm (EMBFA) to solve the problem GSSSP under certain given conditions. Thirdly, introduce a few concepts, such as order-preserving in last road (OPLR) of path function, and so on. And under the assumption that the value of related path function for any path can be obtained in $M(n)$ time, prove respectively the algorithm EDA solving the problem GSSSP in $O(n^2)M(n)$ time and the algorithm EMBFA solving the problem GSSSP in $O(mn)M(n)$ time. Finally, some applications of the designed algorithms are shown with a few examples. What we done can improve both the researchers and the applications of the shortest path theory.

There is a growing need for vehicle positioning information to support Advanced Driver Assistance Systems (ADAS), Connectivity (V2X), and Autonomous Driving (AD) features. These range from a need for road determination ($<$5 meters), lane determination ($<$1.5 meters), and determining where the vehicle is within the lane ($<$0.3 meters). This paper presents the Ford Highway Driving RTK (Ford-HDR) dataset. This dataset includes nearly 30,000 km of data collected primarily on North American highways during a driving campaign designed to validate driver assistance features in 2018. This includes data from a representative automotive production GNSS used primarily for turn-by-turn navigation as well as an Inertial Navigation System (INS) which couples two survey-grade GNSS receivers with a tactical grade Inertial Measurement Unit (IMU) to act as ground truth. The latter utilized networked Real-Time Kinematic (RTK) GNSS corrections delivered over a cellular modem in real-time. This dataset is being released into the public domain to spark further research in the community.

An amusing connection between Ford circles, Fibonacci numbers, and golden ratio is shown. Namely, certain tangency points of Ford circles are concyclic and involve Fibonacci numbers. They form four circles that cut the x-axis at points related to the golden ratio.