Planning constrained motion

We consider the motion planning problem for a point constrained to move along a path with radius of curvature at least one. The point moves in a two-dimensional universe with polygonal obstacles. We show the decidability of the reachability question: “Given a source placement (position and direction pair) and a target placement, is there a curvature-constrained path from source to target avoiding obstacles?” The decision procedure has time and space complexity 2 ^{o(poly(n, m))} wheren is the number of corners andm is the number of bits required to specify the position of corners.     

A note on width-parameterized SAT: An exact machine-model characterization

We characterize the complexity of SAT instances with path-decompositions of width w(n). Although pathwidth is the most restrictive among the studied width-parameterizations of SAT, the most time-efficient algorithms known for such SAT instances run in time ²Ω(w(n)), even when the path-decomposition is given in the input. We wish to better understand the decision complexity of SAT instances of width ω(logn). We provide an exact correspondence between SATpw[w(n)], the problem of SAT instances with given path decomposition of width w(n), and NL[r(n)], the class of problems decided by logspace Turing Machines with at most r(n) passes over the nondeterministic tape. In particular, we show that SATpw[w(n)] is hard for under log-space reductions. When is closed under logspace reductions, which is the case for the most interesting w(n)'s, we show that SATpw[w(n)] is also complete.     

A Heuristic for Dijkstra''s Algorithm with Many Targets and Its Use in Weighted Matching Algorithms

Abstract. We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node s and a target set T is specified and the goal is to compute a shortest path from s to a node in T . Our interest in the shortest path problem with many targets stems from its use in weighted bipartite matching algorithms. A weighted bipartite matching in a graph with n nodes on each side reduces to n SSMTSP problems, where the number of targets varies between n and 1 . The SSMTSP problem can be solved by Dijkstra's algorithm. We describe a heuristic that leads to a significant improvement in running time for the weighted matching problem; in our experiments a speed-up by up to a factor of 12 was achieved. We also present a partial analysis that gives some theoretical support for our experimental findings.     

Online chasing problems for regular polygons

We consider a server location problem with only one server to move. In this paper we assume that a request is given as a region and that the service can be done anywhere inside the region. Namely, for each request an online algorithm chooses an arbitrary point in the region and moves the server there. Note that if every request is a single point and the server must exactly go there in the given order as conventional server problems, there is no choice for the online player and the problem is trivial. Our main result shows that if the region is a regular n-gon, the competitive ratio of the greedy algorithm is for odd n, and for even n. In particular for a square region, the greedy algorithm turns out to be optimal.     

Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable

Recognition of minimal unsatisfiable CNF formulas (unsatisfiable CNF formulas which become satisfiable if any clause is removed) is a classical D^P-complete problem. It was shown recently that minimal unsatisfiable formulas with n variables and n+k clauses can be recognized in time . We improve this result and present an algorithm with time complexity ; hence the problem turns out to be fixed-parameter tractable (FTP) in the sense of Downey and Fellows (Parameterized Complexity, 1999).Our algorithm gives rise to a fixed-parameter tractable parameterization of the satisfiability problem: If for a given set of clauses F, the number of clauses in each of its subsets exceeds the number of variables occurring in the subset at most by k, then we can decide in time whether F is satisfiable; k is called the maximum deficiency of F and can be efficiently computed by means of graph matching algorithms. Known parameters for fixed-parameter tractable satisfiability decision are tree-width or related to tree-width. Tree-width and maximum deficiency are incomparable in the sense that we can find formulas with constant maximum deficiency and arbitrarily high tree-width, and formulas where the converse prevails.     

How much precision is needed to compare two sums of square roots of integers?

In this paper, we investigate the problem of the minimum nonzero difference between two sums of square roots of integers. Let r(n,k) be the minimum positive value of where ai and bi are integers not larger than integer n. We prove by an explicit construction that r(n,k)=O(n−2k+3/2) for fixed k and any n. Our result implies that in order to compare two sums of k square roots of integers with at most d digits per integer, one might need precision of as many as digits. We also prove that this bound is optimal for a wide range of integers, i.e., r(n,k)=Θ(n−2k+3/2) for fixed k and for those integers in the form of and , where n^′ is any integer satisfied the form and i is any integer in [0,k−1]. We finally show that for k=2 and any n, this bound is also optimal, i.e., r(n,2)=Θ(n−7/2).     

A fast algorithm for the alpha-connected two-center decision problem

This paper considers the problem of determining whether a set of points can be covered by two discs with centers p and q and common radius r, such that the ratio d(p,q)/r is bounded below by a specified constant, α. An O(n²log²n) algorithm for solving this problem is also presented.     

Optimal maintenance policy for multi-component systems under Markovian environment changes

In this paper, we study multi-component systems, which environmental conditions and opportunistic maintenance (OM) involve. Environmental conditions will exert an influence on deterioration processes of the components in the system. For each component, the worse the environmental conditions are, the faster its deterioration speed is. We want to determine when to preventively maintain each component under such environmental influence. Our purpose is to minimize its long-run average maintenance cost. We decompose such a multi-component system into mutually influential single-component systems, and formulate the maintenance problem of each component as a Markov decision process (MDP). Under some reasonable assumptions, we prove the existence of the optimal (n_r, N_r) type policy for each component. A policy iteration method is used to calculate its optimal maintenance policy. Based on the method, we develop an iterative approximation algorithm to obtain an acceptable maintenance policy for a multi-component system. Numerical examples find that environmental conditions and OM pose significant effects on a maintenance policy.     

Threshold behaviors of a random constraint satisfaction problem with exact phase transitions

We consider a random constraint satisfaction problem named model RB, which exhibits a sharp satisfiability phase-transition phenomenon when the control parameters pass through the critical values denoted by rcr and pcr. Using finite-size scaling analysis, we bound the width of the transition region for finite problem size n, which might be the first rigorous study on the threshold behaviors of NP-complete problems.     

A practical approximation algorithm for the LMS line estimator

The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Robust estimators are widely used because of their lack of sensitivity to outlying data points. The least median-of-squares (LMS) regression line estimator is among the best known robust estimators. Given a set of n points in the plane, it is defined to be the line that minimizes the median squared residual or, more generally, the line that minimizes the residual of any given quantile q, where 0<q?1. This problem is equivalent to finding the strip defined by two parallel lines of minimum vertical separation that encloses at least half of the points.The best known exact algorithm for this problem runs in O(n²) time. We consider two types of approximations, a residual approximation, which approximates the vertical height of the strip to within a given error bound ε_r?0, and a quantile approximation, which approximates the fraction of points that lie within the strip to within a given error bound ε_q?0. We present two randomized approximation algorithms for the LMS line estimator. The first is a conceptually simple quantile approximation algorithm, which given fixed q and ε_q>0 runs in O(nlogn) time. The second is a practical algorithm, which can solve both types of approximation problems or be used as an exact algorithm. We prove that when used as a quantile approximation, this algorithm's expected running time is . We present empirical evidence that the latter algorithm is quite efficient for a wide variety of input distributions, even when used as an exact algorithm.     

On a circle placement problem

We consider the following circle placement problem: given a set of pointsp _i ,i=1,2, ...,n, each of weightw _i , in the plane, and a fixed disk of radiusr, find a location to place the disk such that the total weight of the points covered by the disk is maximized. The problem is equivalent to the so-called maximum weighted clique problem for circle intersection graphs. That is, given a setS ofn circles,D _i ,i=1,2, ...,n, of the same radiusr, each of weightw _i , find a subset ofS whose common intersection is nonempty and whose total weight is maximum. AnO (n ²) algorithm is presented for the maximum clique problem. The algorithm is better than a previously known algorithm which is based on sorting and runs inO (n ² logn) time.     

Static and dynamic minimum energy broadcast problem in wireless ad-hoc networks: A PSO-based approach and analysis

In this paper, we address the minimum energy broadcast (MEB) problem in wireless ad-hoc networks (WANETs). The researches in WANETs have attracted significant attentions, and one of the most critical issues in WSNs is minimization of energy consumption. In WANETs the packets have to be transported from a given source node to all other nodes in the network, and the objective of the MEB problem is to minimize the total transmission power consumption. A hybrid algorithm based on particle swarm optimization (PSO) and local search is presented to solve the MEB problem. A power degree encoding is proposed to reflect the extent of transmission power level and is used to define the particle position in PSO. We also analyze a well-known local search mechanism, r-shrink, and propose an improved version, the intensified r-shrink. In order to solve the dynamic MEB problem with node removal/insertion, this paper provides an effective simple heuristic, Conditional Incremental Power (CIP), to reconstruct the broadcast network efficiently. The promising results indicate the potential of the proposed methods for practical use.     

Load-dependent and precedence-based models for pickup and delivery problems

We address the one-to-one multi-commodity pickup and delivery traveling salesman problem (m-PDTSP) which is a generalization of the TSP and arises in several transportation and logistics applications. The objective is to find a minimum-cost directed Hamiltonian path which starts and ends at given depot nodes and such that the demand of each given commodity is transported from the associated source to its destination and the vehicle capacity is never exceeded. In contrast, the many-to-many one-commodity pickup and delivery traveling salesman problem (1-PDTSP) just considers a single commodity and each node can be a source or target for units of this commodity. We show that the m-PDTSP is equivalent to the 1-PDTSP with additional precedence constraints defined by the source–destination pairs for each commodity and explore several models based on this equivalence. In particular, we consider layered graph models for the capacity constraints and introduce new valid inequalities for the precedence relations. Especially for tightly capacitated instances with a large number of commodities our branch-and-cut algorithms outperform the existing approaches. For the uncapacitated m-PDTSP (which is known as the sequential ordering problem) we are able to solve to optimality several open instances from the TSPLIB and SOPLIB.     

On generalized middle-level problem

Let be the subgraph of the hypercube Q_n induced by levels between k and n-k, where n?2k+1 is odd. The well-known middle-level conjecture asserts that is Hamiltonian for all k?1. We study this problem in for fixed k. It is known that and are Hamiltonian for all odd n?3. In this paper we prove that also is Hamiltonian for all odd n?5, and we conjecture that is Hamiltonian for every k?0 and every odd n?2k+1.     

Sensor scheduling for target tracking: A Monte Carlo sampling approach

We study the problem of sensor-scheduling for target tracking—to determine which sensors to activate over time to trade off tracking performance with sensor usage costs. We approach this problem by formulating it as a partially observable Markov decision process (POMDP), and develop a Monte Carlo solution method using a combination of particle filtering for belief-state estimation and sampling-based Q-value approximation for lookahead. To evaluate the effectiveness of our approach, we consider a simple sensor-scheduling problem involving multiple sensors for tracking a single target.     

Improving the running time of embedded upward planarity testing

We consider the standard algorithm by Bertolazzi et al. to test the upward planarity of embedded digraphs. We show how to improve its running time from O(n+r²) to , where r is the number of sources and sinks in the digraph. We also discuss an application of this technique: improving the running time of getting a quasi-upward planar drawing for an embedded digraph with minimum number of bends.     

On Some Proximity Problems of Colored Sets

The maximum diameter color-spanning set problem（MaxDCS） is defined as follows： given n points with m colors, select m points with m distinct colors such that the diameter of the set of chosen points is maximized. In this paper, we design an optimal O（n log n） time algorithm using rotating calipers for MaxDCS in the plane. Our algorithm can also be used to solve the maximum diameter problem of imprecise points modeled as polygons. We also give an optimal algorithm for the all farthest foreign neighbor problem（AFFN） in the plane, and propose algorithms to answer the farthest foreign neighbor query（FFNQ） of colored sets in two- and three-dimensional space. Furthermore, we study the problem of computing the closest pair of color-spanning set（CPCS） in d-dimensional space, and remove the log m factor in the best known time bound if d is a constant.