Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games

We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of all satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. While the proposed algorithm guarantees progress and soundness in every iteration, it is computationally demanding. We offer an alternative, more efficient solution for the reachability properties that decomposes the problem into a series of smaller problems of the same type. All algorithms are demonstrated on an illustrative case study.     

Envy-free matchings with one-sided preferences and matroid constraints

In this paper, we consider the problem of checking the existence of an envy-free matching in a many-to-one matching model with one-sided preferences and matroid constraints. For this problem, we propose a polynomial-time algorithm which is a generalization of the algorithm proposed by Gan, Suksompong, and Voudouris for the one-to-one setting. Furthermore, we consider a stronger variant of envy-freeness.     

Approximating the least core value and least core of cooperative games with supermodular costs

We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on oracles that approximately determine maximally violated constraints. This framework yields a 3-approximation algorithm for computing the least core value of supermodular cost cooperative games, and a polynomial-time algorithm for computing a cost allocation in the 2-approximate least core of these games. This approximation framework extends naturally to submodular profit cooperative games. For scheduling games, a special class of supermodular cost cooperative games, we give a fully polynomial-time approximation scheme for computing the least core value. For matroid profit games, a special class of submodular profit cooperative games, we give exact polynomial-time algorithms for computing the least core value as well as a least core cost allocation.     

广义二分搜索及其在 LP 多项式算法复杂度证明中的应用

Khachiyan 和 Karmarkar 方法的提出,不仅解决了长期悬而未决的线性规划(LP)问题的多项式时间算法的存在性问题,而且开辟了优化算法设计上新的方法论体系.目前的兴趣之一是把这一方法论体系应用到一般的连续优化问题中去.一个组合优化问题,同一般优化问题一样,可以表达成一个二元组((?),c),其中(?)是可行解集合,c 是定义在(?)上的实目标函数.对于组合问题,一般地,(?)是离     

The base of the intersection of two free submonoids

Given two free submonoids of a free monoid, one wishes to find a specification for the base of the intersection. An algorithm to construct a graph-theoretic specification of the base is presented. From this specification it can easily be determined whether the base is finite. In addition, a a polynomial-time algorithm to determine if a regular set is a circular code is presented.     

A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization

We propose a polynomial-time-delay polynomial-space algorithm to enumerate all efficient extreme solutions of a multi-criteria minimum-cost spanning tree problem, while only the bi-criteria case was studied in the literature. The algorithm is based on the reverse search framework due to Avis and Fukuda. We also show that the same technique can be applied to the multi-criteria version of the minimum-cost basis problem in a (possibly degenerated) submodular system. As an ultimate generalization, we propose an algorithm to enumerate all efficient extreme solutions of a multi-criteria linear program. When the given linear program has no degeneracy, the algorithm runs in polynomial-time delay and polynomial space. To best of our knowledge, they are the first polynomial-time delay and polynomial-space algorithms for the problems.     

Time-constrained temporal logic control of multi-affine systems

In this paper, we consider the problem of controlling a dynamical system such that its trajectories satisfy a temporal logic property in a given amount of time. We focus on multi-affine systems and specifications given as syntactically co-safe linear temporal logic formulas over rectangular regions in the state space. The proposed algorithm is based on estimating the time bounds for facet reachability problems and solving a time optimal reachability problem on the product between a weighted transition system and an automaton that enforces the satisfaction of the specification. A random optimization algorithm is used to iteratively improve the solution.     

Bandwidth of bipartite permutation graphs in polynomial time

We give the first polynomial-time algorithm that computes the bandwidth of bipartite permutation graphs. Bandwidth is an NP-complete graph layout problem that is notorious for its difficulty even on small graph classes. For example, it remains NP-complete on caterpillars of hair length at most 3, a very restricted subclass of trees. Much attention has been given to designing approximation algorithms for computing the bandwidth, as it is NP-hard to approximate the bandwidth of general graphs with a constant factor guarantee. The problem is considered important even for approximation on restricted classes, with several distinguished results in this direction. Prior to our work, polynomial-time algorithms for exact computation of bandwidth were known only for caterpillars of hair length at most 2, chain graphs, cographs, and most interestingly, interval graphs.     

Algorithmic Chernoff-Hoeffding inequalities in integer programming

Proofs of classical Chernoff-Hoeffding bounds has been used to obtain polynomial-time implementations of Spencer's derandomization method of conditional probabilities on usual finite machine models: given m events whose complements are large deviations corresponding to weighted sums of n mutually independent Bernoulli trials. Raghavan's lattice approximation algorithm constructs for 0-1 weights, and integer deviation terms in O(mn)-time a point for which all events hold. For rational weighted sums of Bernoulli trials the lattice approximation algorithm or Spencer's hyperbolic cosine algorithm are deterministic precedures, but a polynomial-time implementation was not known. We resolve this problem with an O(mn²log $ {{mn}\over{\epsilon}} $)-time algorithm, whenever the probability that all events hold is at least ϵ > 0. Since such algorithms simulate the proof of the underlying large deviation inequality in a constructive way, we call it the algorithmic version of the inequality. Applications to general packing integer programs and resource constrained scheduling result in tight and polynomial-time approximations algorithms. © 1996 John Wiley & Sons, Inc.     

Shorter tours by nicer ears: 7/5-Approximation for the graph-TSP, 3/2 for the path version,and 4/3 for two-edge-connected subgraphs

We prove new results for approximating the graph-TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees. For the graph-TSP itself, we improve the approximation ratio to 7=5. For a generalization, the minimum T-tour problem, we obtain the first nontrivial approximation algorithm, with ratio 3=2. This contains the s-t-path graph-TSP as a special case. Our approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4=3. The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP relaxations) that we use to deduce the approximation ratios.     

Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem

M-convex functions, introduced by Murota (Adv. Math. 124 (1996) 272; Math. Prog. 83 (1998) 313), enjoy various desirable properties as “discrete convex functions.” In this paper, we propose two new polynomial-time scaling algorithms for the minimization of an M-convex function. Both algorithms apply a scaling technique to a greedy algorithm for M-convex function minimization, and run as fast as the previous minimization algorithms. We also specialize our scaling algorithms for the resource allocation problem which is a special case of M-convex function minimization.     

Approximation algorithms for the Euclidean bipartite TSP

We study approximation results for the Euclidean bipartite traveling salesman problem (TSP). We present the first worst-case examples, proving that the approximation guarantees of two known polynomial-time algorithms are tight. Moreover, we propose a new algorithm which displays a superior average case behavior indicated by computational experiments.     

Sparse pseudorandom distributions

The existence of sparse pseudorandom distributions is proved. These are probability distributions concentrated in a very small set of strings, yet it is infeasible for any polynomial-time algorithm to distinguish between truly random coins and coins selected according to these distributions. It is shown that such distributions can be generated by (nonpolynomial) probabilistic algorithms, while probabilistic polynomial-time algorithms cannot even approximate all the pseudorandom distributions. Moreover, we show the existence of evasive pseudorandom distributions which are not only sparse, but also have the property that no polynomial-time algorithm may find an element in their support, except for a negligible probability. All these results are proved independently of any intractability assumption.     

An iterative back substitution algorithm for the solution of tridiagonal matrix systems with fringes

For tridiagonal matrix systems, a simple direct algorithm giving the solution exists, but in the most general case of tridiagonal matrix with fringes, the direct solving algorithms are more complicated. For big systems, direct methods are not well fitted and iterative algorithms are preferable. In this paper a relaxation type iterative algorithm is presented. It is an extension of the backward substitution method used for simple tridiagonal matrix systems. The performances show that this algorithm is a good compromise between a direct method and other iterative methods as block SOR. Its nature suggests its use as inner solver in the solution of problems derived by application of a decomposition domain method. A special emphasis is done on the programming aspect. The solving Fortran subroutines implementing the algorithm have been generated automatically from their specification by using a computer algebra system technique.     

Automatic validation and failure diagnosis of human-device interfaces using task analytic models and model checking

When evaluating designs of human-device interfaces for safety critical systems, it is very important that they support the goal-directed tasks they were designed to facilitate. This paper describes a novel method that generates task-related temporal logic properties from task analytic models created early in the system design process. This allows analysts to use model checking (a means of performing exhaustive mathematical proofs) to automatically validate that formal models of human-device interfaces will let human operators successfully perform the necessary tasks with the system. This paper also presents an algorithm that uses the method to diagnose why a particular task is not valid for a given design. The application of both the method and algorithm are illustrated with a patient-controlled analgesia pump programming example. The method and algorithm are discussed and avenues for future work are described.     

Funnel control for fully actuated systems under a fragment of signal temporal logic specifications

Temporal logics have lately proven to be a valuable tool for various control applications by providing a rich specification language. Existing temporal logic-based control strategies discretize the underlying dynamical system in space and/or time. We will not use such an abstraction and consider continuous-time systems under a fragment of signal temporal logic specifications by using the associated robust semantics. In particular, this paper provides computationally-efficient funnel-based feedback control laws for a class of systems that are, in a sense, feedback equivalent to single integrator systems, but where the dynamics are partially unknown for the control design so that some degree of robustness is obtained. We first leverage the transient properties of a funnel-based feedback control strategy to maximize the robust semantics of some atomic temporal logic formulas. We then guarantee the satisfaction for specifications consisting of conjunctions of such atomic temporal logic formulas with overlapping time intervals by a suitable switched control system. The result is a framework that satisfies temporal logic specifications with a user-defined robustness when the specification is satisfiable. When the specification is not satisfiable, a least violating solution can be found. The theoretical findings are demonstrated in simulations of the nonlinear Lotka–Volterra equations for predator–prey models.     

Guaranteed performance heuristics for the bottleneck travelling salesman problem

We consider constant-performance, polynomial-time, nonexact algorithms for the minimax or bottleneck version of the Travelling Salesman Problem. It is first shown that no such algorithm can exist for problems with arbitrary costs unless P = NP. However, when costs are positive and satisfy the triangle inequality, we use results pertaining to the squares of biconnected graphs to produce a polynomial-time algorithm with worst-case bound 2 and show further that, unless P = NP, no polynomial alternative can improve on this value.     

A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case

In this paper we consider the problem of no-wait cyclic scheduling of identical parts in an m-machine production line in which a robot is responsible for moving each part from a machine to another. The aim is to find the minimum cycle time for the so-called 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. The earlier known polynomial-time algorithms for this problem are applicable only under the additional assumption that the robot travel times satisfy the triangle inequalities. We lift this assumption on robot travel times and present a polynomial-time algorithm with the same time complexity as in the metric case, O(m⁵logm).     

Lot-sizing with non-stationary cumulative capacities

We study a new class of capacitated economic lot-sizing problems. We show that the problem is NP-hard in general and derive a fully polynomial-time approximation algorithm under mild conditions on the cost functions. Furthermore, we develop a polynomial-time algorithm for the case where all cost functions are concave.