nils-herrmann/clean_scirepeval huggingface dataset:
Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows

Minimum cost multicommodity flow is an instance of a simpler problem (multicommodity flow) to which a cost constraint has been added. In this paper we present a general scheme for solving a large class of such “cost-added” problems—even if more than one cost is added. One of the main applications of this method is a new deterministic algorithm for approximately solving the minimumcost multicommodity flow problem. Our algorithm finds a (1 + e) approximation to the minimum cost flow in 0(e-3kmn) time, where k is the number of commodities, m is the number of edges, and n is the number vertices in the input problem. This improves the previous best deterministic bounds of O(e-4kmn2 )  and 6(e-2k2m2)  by f~ctors of n/6 and ekm/n respectively. In fact, it even dominates the best randomized bound of 0(e-2km2) . The algorithm presented in this paper efficiently solves several other interesting generalizations of rein-cost flow problems, such as one in which each commodity can have its own distinct shipping cost per edge, or one in which there is more than one cost measure on the flows and all costs must be kept small simultaneously. Our approach is based on an extension of the approximate packing techniques in  and a generalization of the round-robin approach of [16] to multicommodity flow without costs.
A randomized fully polynomial time approximation scheme for the all terminal network reliability problem

The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This problem has obvious ap- plications in the design of communication networks. Since the problem isP-complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approxima- tion scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and 1/� an estimate for the failure probability that is accurate to within a relative error of 1 ± � with high probability. We also give a deterministic polyno- mial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of k-connectivity, strong connectivity in directed Eulerian graphs and r-way disconnection, and to evaluating the Tutte polynomial are also described. This version of the paper corrects several errata that appeared in the previous journal publication (D. R. Karger,  (1999), pp. 492-514).
Random sampling in graph optimization problems

The representative random sample is a central concept of statistics. It is often possible to gather a great deal of information about a large population by examining a small sample randomly drawn from it. This approach has obvious advantages in reducing the investigator's work, both in gathering and in analyzing the data. 
We apply the concept of a representative sample to combinatorial optimization. Our general technique is to generate small random representative subproblems and solve them in lieu of the original ones, producing approximately correct answers which may then be refined to correct ones at little additional cost. Our focus is optimization problems on undirected graphs. Highlights of our results include: (1) The first (randomized) linear time minimum spanning tree algorithm; (2) A (randomized) minimum cut algorithm with running time roughly $O(n\sp2)$ as compared to previous roughly $O(n\sp3)$ time bounds, as well as the first algorithm for finding all approximately minimal cuts and multiway cuts; (3) An efficient parallelization of the minimum cut algorithm, providing the first parallel $({\cal RNC})$ algorithm for minimum cuts, together with a derandomization proving that minimum cuts can be found deterministically in parallel $({\cal NC})$; (4) Tight bounds on the all terminal reliability (probability of remaining connected) of a network suffering random edge failures. (5) Linear time sequential and linear processor parallel algorithms for finding approximately minimum cuts; (6) Faster algorithms for approximating and exactly finding s-t minimum cuts and maximum flows; (7) For the ${\cal NP}$-complete problem of designing minimum cost networks satisfying specified connectivity requirements (a generalization of the minimum spanning tree problem), significantly improved polynomial-time approximation bounds (from $O(\log n)$ to 1 + o(1) for many such problems); (8) For coloring 3-colorable graphs, improvements in the polynomial time approximation bounds from O($n\sp{3/8})$ to O($n\sp{1/4}),$ and even better bounds for sparse graphs; (9) An analysis of random sampling in matroids.
Prim-Dijkstra tradeoffs for improved performance-driven routing tree design

Analysis of Elmore delay in distributed RC tree structures shows the influence of both tree cost and tree radius on signal delay in VLSI interconnects. We give new and efficient interconnection tree constructions that smoothly combine the minimum cost and the minimum radius objectives, by combining respectively optimal algorithms due to Prim (1957) and Dijkstra (1959). Previous "shallow-light" techniques are both less direct and less effective: in practice, our methods achieve uniformly superior cost-radius tradeoffs. Timing simulations for a range of IC and MCM interconnect technologies show that our wirelength savings yield reduced signal delays when compared to shallow-light or standard minimum spanning tree and Steiner tree routing.
Scatter/Gather as a Tool for the Navigation of Retrieval Results

An important information access problem arises when the user is confronted with a very large number of documents that have been retrieved in response to a query. In this paper we explore the use of a technique, called Scatter/Gather, for the navigation of large collections of retrieved documents. Scatter/Gather clusters the documents into semantically coherent groups on-the-fly and presents descriptive summaries of the groups to the user. These groups can be used in several ways: to identify useful subsets of documents to be perused with other tools, to eliminate subsets whose contents appear nonrelevant, or to select promising document subsets for reclustering into more refined groups. This paper describes the Scatter/Gather algorithm and illustrates its application to retrieval results via two examples.
Visibility-based Pursuit-evasion with Limited Field of View

We study the visibility-based pursuit-evasion problem, in which one or more searchers must move through a given environment so as to guarantee detection of any and all evaders, which can move arbitrarily fast. Our goal is to develop techniques for coordinating teams of robots to execute this task in application domains such as clearing a building, for reasons of security or safety. To this end, we introduce a new class of searcher, the φ-searcher, which can be readily instantiated as a physical mobile robot. We present a detailed analysis of the pursuit-evasion problem using φ-searchers. We present the first complete search algorithm for a single φ-searcher, show how this algorithm can be extended to handle multiple searchers, and give examples of computed trajectories.
A Distributed Approach to Passive Localization for Sensor Networks

Sensors that know their location, from microphones to vibration sensors, can support a wider arena of applications than their location unaware counterparts. We offer a method for sensors to determine their own location relative to one another by using only exogenous sounds and the differences in the arrivals of these sounds at different sensors. We present a distributed and computationally efficient solution that offers accuracy on par with more active and computationally intense methods.
Affine Structure From Sound

We consider the problem of localizing a set of microphones together with a set of external acoustic events (e.g., hand claps), emitted at unknown times and unknown locations. We propose a solution that approximates this problem under a far field approximation defined in the calculus of affine geometry, and that relies on singular value decomposition (SVD) to recover the affine structure of the problem. We then define low-dimensional optimization techniques for embedding the solution into Euclidean geometry, and further techniques for recovering the locations and emission times of the acoustic events. The approach is useful for the calibration of ad-hoc microphone arrays and sensor networks.
Basic Set Definitions

Robot motion planning has become a major focus of robotics. Research findings can be applied not only to robotics but to planning routes on circuit boards, directing digital actors in computer graphics, robot-assisted surgery and medicine, and in novel areas such as drug design and protein folding. This text reflects the great advances that have taken place in the last ten years, including sensor-based planning, probabalistic planning, localization and mapping, and motion planning for dynamic and nonholonomic systems. Its presentation makes the mathematical underpinnings of robot motion accessible to students of computer science and engineering, rleating low-level implementation details to high-level algorithmic concepts.
Parallel Stochastic Hill- Climbing with Small Teams

We address the basic problem of coordinating the actions of multiple robots that are working toward a common goal. This kind of problem is NP-hard, because in order to coordinate a system of n robots, it is in principle necessary to generate and evaluate a number of actions or plans that is exponential in n (assuming P ≠ NP). However, we suggest that many instances of coordination problems, despite the NP-hardness of the overall class of problems, do not in practice require exponential computation in order to arrive at good solutions. In such problems, it is not necessary to consider all possible actions of the n robots; instead an algorithm may restrict its attention to interactions within small teams, and still produce high-quality solutions.
Search-based planning for large dynamic environments

Agents operating in the real world often have to act under the conditions where time is critical: there is a limit on the time they can afford to spend on deliberating what action to execute next. Planners used by such agents must produce the best plans they can find within the amount of time available. The strategy of always searching for an optimal plan becomes infeasible in these scenarios. Instead, we must use an anytime planner. Anytime planners operate by quickly finding a highly suboptimal plan first, and then improving it until the available time runs out. 
In addition to the constraints on time, world models used by planners are usually imperfect and environments are often dynamic. The execution of a plan therefore often results in unexpected outcomes. An agent then needs to update the model accordingly and re-execute a planner on the new model. A planner that has a replanning capability (a.k.a. an incremental planner) can substantially speed up each planning episode in such cases, as it tries to make use of the results of previous planning efforts in finding a new plan. 
Combining anytime with replanning capabilities is thus beneficial. For one, at each planning episode it allows the planner to produce a better plan within the available time: both in finding the first plan as well as in improving it, the planner can use its replanning capability to accelerate the process. In addition, the combination allows one to interleave planning and execution effectively. While the agent executes the current plan, the planner can continue improving it without having to discard all of its efforts every time the model of the world is updated. 
This thesis concentrates on graph-based searches. It presents an alternative view of A* search, a widely popular heuristic search in AI, and then uses this view to easily derive three versions of A* search: an anytime version, an incremental version and a version that is both anytime and incremental. Each of these algorithms is also able to provide a non-trivial bound on the suboptimality of the solution it generates. We believe that the simplicity, the existence of suboptimality bounds and the generality of the presented methods contribute to the research and development of planners well suited for systems operating in the real world.
Learning Motion Patterns of People for Compliant Robot Motion

Whenever people move through their environments they do not move randomly. Instead, they usually follow specific trajectories or motion patterns corresponding to their intentions. Knowledge about such patterns enables a mobile robot to robustly keep track of persons in its environment and to improve its behavior. In this paper we propose a technique for learning collections of trajectories that characterize typical motion patterns of persons. Data recorded with laser-range finders are clustered using the expectation maximization algorithm. Based on the result of the clustering process, we derive a hidden Markov model that is applied to estimate the current and future positions of persons based on sensory input. We also describe how to incorporate the probabilistic belief about the potential trajectories of persons into the path planning process of a mobile robot. We present several experiments carried out in different environments with a mobile robot equipped with a laser-range scanner and a camera system. The results demonstrate that our approach can reliably learn motion patterns of persons, can robustly estimate and predict positions of persons, and can be used to improve the navigation behavior of a mobile robot.
A probabilistic language based upon sampling functions

As probabilistic computations play an increasing role in solving various problems, researchers have designed probabilistic languages that treat probability distributions as primitive datatypes. Most probabilistic languages, however, focus only on discrete distributions and have limited expressive power. In this paper, we present a probabilistic language, called λο, which uniformly supports all kinds of probability distributions -- discrete distributions, continuous distributions, and even those belonging to neither group. Its mathematical basis is sampling functions, i.e., mappings from the unit interval (0.0,1.0] to probability domains.We also briefly describe the implementation of λο as an extension of Objective CAML and demonstrate its practicality with three applications in robotics: robot localization, people tracking, and robotic mapping. All experiments have been carried out with real robots.
Game Theoretic Control for Robot Teams

In the real world, noisy sensors and limited communication make it difficult for robot teams to coordinate in tightly coupled tasks. Team members cannot simply apply single-robot solution techniques for partially observable problems in parallel because they do not take into account the recursive effect that reasoning about the beliefs of others has on policy generation. Instead, we must turn to a game theoretic approach to model the problem correctly. Partially observable stochastic games (POSGs) provide a solution model for decentralized robot teams, however, this model quickly becomes intractable. In previous work we presented an algorithm for lookahead search in POSGs. Here we present an extension which reduces computation during lookahead by clustering similar observation histories together. We show that by clustering histories which have similar profiles of predicted reward, we can greatly reduce the computation time required to solve a POSG while maintaining a good approximation to the optimal policy. We demonstrate the power of the clustering algorithm in a real-time robot controller as well as for a simple benchmark problem.
Change Detection From Multiple Camera Images Extended to Non-Stationary Cameras

We describe an approach for analysis of surveillance video taken from moving vehicles making repeated passes through a specific, well-defined corridor. Our goal is to detect stationary objects which have appeared in scenes along the established route. Our motivation is to address security concerns in hostile theaters where stationary surveillance cameras would be destroyed almost immediately; yet mobile camera platforms; i.e., group transport vehicles/convoys are plentiful. Challenges include illumination changes from different time/day, and handling parallax resulting from our non-stationary camera. We provide an example using artificial surveillance images taken on the Stanford University campus. Scale-up to critical security theaters would be straightforward. The approach is equally applicable to images collected by aircraft.
A Non-rigid Approach to Scan Alignment and Change Detection Using Range Sensor Data

We present a probabilistic technique for alignment and subsequent change detection using range sensor data. The alignment method is derived from a novel, non-rigid approach to register point clouds induced by pose-related range observations that are particularly erroneous. It allows for high scan estimation errors to be compensated distinctly, whilst considering temporally successive measurements to be correlated. Based on the alignment, changes between data sets are detected using a probabilistic approach that is capable of differentiating between likely and unlikely changes. When applied to observations containing even small differences, it reliably identifies intentionally introduced modifications.
A programming language for probabilistic computation

As probabilistic computations play an increasing role in solving various problems, researchers have designed probabilistic languages to facilitate their modeling. Most of the existing probabilistic languages, however, focus only on discrete distributions, and there has been little effort to develop probabilistic languages whose expressive power is beyond discrete distributions. This dissertation presents a probabilistic language, called PTP (ProbabilisTic Programming), which supports all kinds of probability distributions. 
The key idea behind PTP is to use sampling functions, i.e., mappings from the unit interval (0.0,1.0] to probability domains, to specify probability distributions. By using sampling functions as its mathematical basis, PTP provides a unified representation scheme for probability distributions, without drawing a syntactic or semantic distinction between different kinds of probability distributions. 
Independently of PTP, we develop a linguistic framework, called λ c, to account for computational effects in general. λ c extends a monadic language by applying the possible world interpretation of modal logic. A characteristic feature of λc is the distinction between stateful computational effects, called world effects , and contextual computational effects, called control effects . PTP arises as an instance of λc with a language construct for probabilistic choices. 
We use a sound and complete translator of PTP to embed it in Objective CAML. The use of PTP is demonstrated with three applications in robotics: robot localization, people tracking, and robotic mapping. Thus PTP serves as another example of high-level language applied to a problem domain where imperative languages have been traditionally dominant.
The Information-Form Data Association Filter

This paper presents a new filter for online data association problems in high-dimensional spaces. The key innovation is a representation of the data association posterior in information form, in which the "proximity" of objects and tracks are expressed by numerical links. Updating these links requires linear time, compared to exponential time required for computing the exact posterior probabilities. The paper derives the algorithm formally and provides comparative results using data obtained by a real-world camera array and by a large-scale sensor network simulation.
An Application of Markov Random Fields to Range Sensing

This paper describes a highly successful application of MRFs to the problem of generating high-resolution range images. A new generation of range sensors combines the capture of low-resolution range images with the acquisition of registered high-resolution camera images. The MRF in this paper exploits the fact that discontinuities in range and coloring tend to co-align. This enables it to generate high-resolution, low-noise range images by integrating regular camera images into the range data. We show that by using such an MRF, we can substantially improve over existing range imaging technology.
Adaptive Road Following using Self-Supervised Learning and Reverse Optical Flow

The majority of current image-based road following algorithms operate, at least in part, by assuming the presence of structural or visual cues unique to the roadway. As a result, these algorithms are poorly suited to the task of tracking unstructured roads typical in desert environments. In this paper, we propose a road following algorithm that operates in a selfsupervised learning regime, allowing it to adapt to changing road conditions while making no assumptions about the general structure or appearance of the road surface. An application of optical flow techniques, paired with one-dimensional template matching, allows identification of regions in the current camera image that closely resemble the learned appearance of the road in the recent past. The algorithm assumes the vehicle lies on the road in order to form templates of the road’s appearance. A dynamic programming variant is then applied to optimize the 1-D template match results while enforcing a constraint on the maximum road curvature expected. Algorithm output images, as well as quantitative results, are presented for three distinct road types encountered in actual driving video acquired in the California Mojave Desert.
PARALLEL STOCHASTIC HILLCLIMBING WITH SMALL TEAMS

We address the basic problem of coordinating the actions of multiple robots that are working toward a common goal. This kind of problem is NP-hard, because in order to coordinate a system of n robots, it is in principle necessary to generate and evaluate a number of actions or plans that is exponential in n (assuming P 6= NP ). However, we suggest that many instances of coordination problems, despite the NP-hardness of the overall class of problems, do not in practice require exponential computation in order to arrive at good solutions. In such problems, it is not necessary to consider all possible actions of the n robots; instead an algorithm may restrict its attention to interactions within small teams, and still produce high-quality solutions. We use this insight in the development of a novel coordination algorithm that we call parallel stochastic hill-climbing with small teams, or Parish. This algorithm is designed specifically for use in multi-robot systems: it can run off-line or on-line, is easily distributed across multiple machines, and is efficient with regard to communication. We state and analyze the Parish algorithm present results from the implementation and application of the algorithm for a concrete problem: multi-robot pursuit-evasion. In this demanding domain, a team of robots must coordinate their actions so as to guarantee location of a skilled evader.
Shape from symmetry

We describe a technique for reconstructing probable occluded surfaces from 3D range images. The technique exploits the fact that many objects possess shape symmetries that can be recognized even from partial 3D views. Our approach identifies probable symmetries and uses them to attend the partial 3D shape model into the occluded space. To accommodate objects consisting of multiple parts, we describe a technique for segmenting objects into parts characterized by different symmetries. Results are provided for a real-world database of 3D range images of common objects, acquired through an active stereo rig