Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One

A cycle cover of a graph is a spanning subgraph, each node of which is part of exactly one simple cycle. A k-cycle cover is a cycle cover where each cycle has length at least k. Given a complete directed graph with edge weights zero and one, Max-k-DDC(0,1) is the problem of finding a k-cycle cover with maximum weight. We present a 2/3 approximation algorithm for Max-k-DDC(0,1) with running time O(n ^5/2). This algorithm yields a 4/3 approximation algorithm for Max-k-DDC(1,2) as well. Instances of the latter problem are complete directed graphs with edge weights one and two. The goal is to find a k-cycle cover with minimum weight. We particularly obtain a 2/3 approximation algorithm for the asymmetric maximum traveling salesman problem with distances zero and one and a 4/3 approximation algorithm for the asymmetric minimum traveling salesman problem with distances one and two. As a lower bound, we prove that Max-k-DDC(0,1) for k 3 and Max-k-UCC(0,1) (finding maximum weight cycle covers in undirected graphs) for k 7 are \APX-complete.     

Comparison of metaheuristics for the k‐labeled spanning forest problem

In this paper, we study the k‐labeled spanning forest (kLSF) problem in which an undirected graph whose edges are labeled and an integer‐positive value are given; the aim is to find a spanning forest of the input graph with the minimum number of connected components and the upper bound on the number of labels. The problem is related to the minimum labeling spanning tree problem and has several applications in the real world. In this paper, we compare several metaheuristics to solve this NP‐hard problem. In particular, the proposed intelligent variable neighborhood search (VNS) shows excellent performance, obtaining high‐quality solutions in short computational running time. This approach integrates VNS with other complementary approaches from machine learning, statistics, and experimental algorithmics, in order to produce high‐quality performance and completely automate the resulting optimization strategy.     

Min‐degree constrained minimum spanning tree problem: complexity,properties, and formulations

This paper addresses a new combinatorial problem, the Min‐Degree Constrained Minimum Spanning Tree (md‐MST), that can be stated as: given a weighted undirected graph with positive costs on the edges and a node‐degrees function , the md‐MST is to find a minimum cost spanning tree T of G, where each node i of T either has at least a degree of or is a leaf node. This problem is closely related to the well‐known Degree Constrained Minimum Spanning Tree (d‐MST) problem, where the degree constraint is an upper bound instead. The general NP‐hardness for the md‐MST is established and some properties related to the feasibility of the solutions for this problem are presented, in particular we prove some bounds on the number of internal and leaf nodes. Flow‐based formulations are proposed and computational experiments involving the associated Linear Programming (LP) relaxations are presented.     

New Condition for FD,All Filters,and New KYP Lemma

This paper presents a necessary and sufficient condition for the fault detection (FD) problem, under a quite general and natural assumption. The condition is actually a constant inertia on the extended imaginary axis (EIA) of a para‐hermitian rational matrix (RM). An observer solution is given. Another two main results are the presentation of all problem solutions, and a necessary and sufficient condition for constant inertia on the EIA or in a given frequency region, for a class of para‐hermitian RMs, in terms of linear matrix inequalities. The latter result can be regarded as a generalization of the Kalman‐Yakubovich‐Popov (KYP) lemma.     

The Mixed Robust /FTS Control Problem Analysis and State Feedback Control

In this paper we deal with the mixed  /finite‐time stability control problem. More specifically, given an open loop uncertain linear system, we provide a necessary and sufficient condition for quadratic input‐output finite‐time stability with an  bound. Exploiting this result we also give a sufficient condition to solve the related synthesis problem via state‐feedback. The property of quadratic input‐output finite‐time stability with an  bound implies that the system under consideration satisfies an  performance bound between the disturbance input and the controlled output and, at the same time, is input‐output finite‐time stable for all admissible uncertainties. This condition requires the solution of a feasibility problem constrained by a pair of differential linear matrix inequalities (LMIs) coupled with a time‐varying LMI. The proposed technique is illustrated by means of both a numerical and a physical example.     

Randomized dining philosophers without fairness assumption

We consider Lehmann-Rabins randomized solution to the well-known problem of the dining philosophers. Up to now, such an analysis has always required a fairness assumption on the scheduling mechanism: if a philosopher is continuously hungry then he must eventually be scheduled. In contrast, we modify here the algorithm in order to get rid of the fairness assumption, and we claim that the spirit of the original algorithm is preserved. We prove that, for any (possibly unfair) scheduling, the modified algorithm converges: every computation reaches with probability 1 a configuration where some philosopher eats. Furthermore, we are now able to evaluate the expected time of convergence in terms of the number of transitions. We show that, for some malicious scheduling, this expected time is at least exponential in the number N of philosophers.Received: 14 June 2002, Accepted: 1 October 2003, Published online: 6 February 2004This paper is a revised and extended version of a communication given by the same authors, at 2nd IFIP Int. Conf. on Theoretical Computer Science (TCS@2002).     

Computing Optimal Diameter-Bounded Polygon Partitions

The minimum -small partition problem is the problem of partitioning a given simple polygon into subpolygons, each with diameter at most , for a given > 0. This paper considers the version of this problem that disallows Steiner points. This problem is motivated by applications in mesh generation and collision detection. The main result in the paper is a polynomial-time algorithm that solves this problem, and either returns an optimal partition or reports the nonexistence of such a partition. This result contrasts with the recent NP-completeness result for the minimum -small partition problem for polygons with holes (C. Worman, 15th Canadian Conference on Computational Geometry, 2003). Even though the running time of our algorithm is a polynomial in the input size, it is prohibitive for most real applications and we seek faster algorithms that approximate an optimal solution. We first present a faster 2-approximation algorithm for the problem for simple polygons and then a near linear-time algorithm for convex polygons that produces, for any > 0, an (+)-small partition with no more polygons than in an optimal -small partition. We also present an exact polynomial-time algorithm for the minimum -small partition problem with the additional constraint that each piece in the partition be convex.     

New interpolation solution and application in system modeling and optimal control with prescribed distance to instability

We present a system theoretic interpretation of a two‐sided interpolation problem with a stable rational matrix U (interpolant) without constraints on its norm. It is known that all solutions U of that problem can be expressed as U = U _h+ U _p, where U _h ranges in the set of all solutions of the associated homogeneous problem, and U _p is a particular solution. We present a new solution for U _p and prove that it is actually the minimal ‐norm interpolant in the set of all interpolants. We apply these results in system modeling and in optimal control of one‐block plants, with a prescribed bound on the distance to instability of the closed‐loop system. The applications are illustrated by examples. Interesting connections to the augmented basic interpolation problem, to Nehari's problem, and to the stability of one‐block plants with multiple unstable invariant zeros are given. Copyright © 2015 John Wiley & Sons, Ltd.     

Robust Stochastic Stability and Control for Uncertain Singular Markovian Jump Systems with Multiplicative Noise

This paper focuses on the problems of robust stability and stabilization and robust control for uncertain singular Markovian jump systems with (x,v)‐dependent noise. The parameter uncertainties appearing in state, input, disturbance as well as diffusion terms are assumed to be time‐varying but norm‐bounded. Based on the approach of generalized quadratic stability, the memoryless state feedback controller is designed for the robust stabilization problem, which ensures that the resulting closed‐loop system has an impulse‐free solution and is asymptotically stable in the mean square. Furthermore, the results of robust control problem are derived. The desired state feedback controller is presented, which not only meets the requirement of robust stabilization but also satisfies a prescribed performance level. The obtained results are formulated in terms of strict LMIs. What we have obtained can be viewed as corresponding extensions of existing results on uncertain singular systems. A numerical example is finally given to demonstrate the application of the proposed method.     

An analysis of parameter adaptation in reactive tabu search

On‐line parameter adaptation schemes are widely used in metaheuristics. They are sometimes preferred to off‐line tuning techniques for two main reasons. First, they promise to achieve good performance even on new instance families that have not been considered during the design or the tuning phase of the algorithm. Second, it is assumed that an on‐line scheme could adapt the algorithm's behaviour to local characteristics of the search space. This paper challenges the second hypothesis by analysing the contribution of the parameter adaptation to the performance of a state‐of‐the‐art reactive tabu search () algorithm for the maximum clique problem. Our experimental analysis shows that this on‐line parameter adaptation scheme converges to good instance‐specific settings for the parameters, and that there is no evidence that it adapts to the local characteristics of the search space. The insights gained from the analysis are confirmed by further experiments with an algorithm for the quadratic assignment problem. Together, the results of the two algorithms shed some new light on the reasons behind the effectiveness of .     

Maximum Dispersion and Geometric Maximum Weight Cliques

We consider a facility location problem, where the objective is to disperse a number of facilities, i.e., select a given number k of locations from a discrete set of n candidates, such that the average distance between selected locations is maximized. In particular, we present algorithmic results for the case where vertices are represented by points in d-dimensional space, and edge weights correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where k is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where k is part of the input, we present a polynomial-time approximation scheme.     

Spatial camera orientation control by rotation‐minimizing directed frames

The use of rotation‐minimizing directed frames (RMDFs) for defining smoothly varying camera orientations along given spatial paths, in real or virtual environments, is proposed. A directed frame on a space curve is a varying orthonormal basis for ℝ³ such that coincides with the unit polar vector from the origin to each curve point, and such a frame is rotation‐minimizing if its angular velocity vector maintains a vanishing component along o . To facilitate computation of rotation‐minimizing directed frames, it is shown that the basic theory is equivalent to the established theory for rotation‐minimizing adapted frames—for which one frame vector coincides with the tangent at each curve point—if one replaces the given space curve by its anti‐hodograph (i.e., indefinite integral). A family of polynomial curves on which RMDFs can be computed exactly by a rational function integration, the Pythagorean (P) curves, is also introduced, together with algorithms for their construction. Copyright © 2009 John Wiley & Sons, Ltd.     

Prize‐collecting set multicovering with submodular pricing

We consider a ground set E and a submodular function acting on it. We first propose a “set multicovering” problem in which the value (price) of any is . We show that the linear program (LP) of this problem can be directly solved by applying a submodular function minimization (SFM) algorithm on the dual LP. However, the main results of this study concern prize‐collecting multicovering with submodular pricing, that is, a more general and more difficult “multicovering” problem in which elements can be left uncovered by paying a penalty. We formulate it as a large‐scale LP (with variables representing all subsets of E) that could be tackled by column generation (CG; for a CG algorithm for “set‐covering” problems with submodular pricing). However, we do not solve this large‐scale LP by CG, but we solve it in polynomial time by exploiting its integrality properties. More exactly, after appropriate restructuring, the dual LP can be transformed into an LP that has been thoroughly studied (as a primal) in the SFM theory. Solving this LP reduces to optimizing a strong map of submodular functions. For this, we use the Fleischer–Iwata framework that optimizes all these functions within the same asymptotic running time as solving a single SFM, that is, in , where and γ is the complexity of one submodular evaluation. Besides solving the problem, the proposed approach can be useful to (a) simultaneously find the best solution of up to functions under strong map relations in time, (b) perform sensitivity analysis in very short time (even at no extra cost), and (c) reveal combinatorial insight into the primal–dual optimal solutions. We present several potential applications throughout the paper, from production planning to combinatorial auctions.     

An iterative algorithm for maximizing robust performance in loop‐shaping design

In this paper, an algorithm that gives the best achievable performance bound on a given control problem is proposed using the loop‐shaping design framework. In view of standard design requirements, the robust performance is maximized at low and high frequencies while keeping the robust stability margin above a specified level, and the robust stability margin is directly improved at mid frequencies (around crossover). The proposed frequency‐dependent optimization problem is cast in an LMI framework. The resulting solution algorithm simultaneously synthesizes loop‐shaping weights and a stabilizing controller that achieve the maximum performance for a given level of robust stability margin corresponding to sufficient gain and phase margins of the closed‐loop system. Copyright © 2012 John Wiley & Sons, Ltd.     

Tractable Decision for a Constraint Language Implies Tractable Search

A constraint satisfaction problem (CSP) instance has a set of variables, each of which can take values in some domain. It also has a set of constraints, each of which restricts the variables in its scope to take values limited by its constraint relation.The language of a constraint satisfaction problem instance is the set of different constraint relations used in its specification. For a given set of relations over some domain we define the problem CSP () to the set of CSP instances whose language is contained in .The decision problem for a set of CSP instances is, given an instance in the class, to decide whether a solution exists. The search problem is to find such a solution. Here we address the connection between the tractability of the decision and search problems. We prove that given a constraint language over a finite domain for which the decision problem for CSP () is tractable, the search problem is always tractable.We define a surjective language over a finite domain in a standard way. We also show that we can determine in polynomial time whether an instance over a surjective language with a tractable decision problem has fewer than k solutions, and that we can generate all of its solutions with polynomial delay.     

A globally asymptotically stabilizing trajectory tracking controller for fully actuated rigid bodies using landmark‐based information

In this paper, we address the problem of designing a control law based on sensor measurements that provides global asymptotic stabilization to a reference trajectory defined on the . The proposed control law is a function of the angular velocity, of vector measurements characterizing the position of some given landmarks, and of their rate of change. We provide sufficient conditions for the existence of synergistic potential functions on SO(3) which are pivotal in the generation of a suitable hybrid control law. We also provide sufficient conditions on the geometry of the landmarks to solve the given problem. Finally, the proposed solution is simulated and compared with a continuous feedback control law. Copyright © 2014 John Wiley & Sons, Ltd.     

optimization‐based fractional‐order PID controllers design

In this paper we propose a fractional‐order proportional‐integral‐derivative controller design based on the solution of an model matching problem for fractional first‐order‐plus‐dead‐time processes. Starting from the analytical solution of the problem, we show that a fractional proportional‐integral‐derivative suboptimal controller can be obtained. Guidelines for the tuning of the controller parameters are given in order to address the robust stability issue and to obtain the required performance. The main differences with respect to the integer‐order case are highlighted. Simulation results show that the design methodology is effective and allows the user to consider process with different dynamics in a unified framework. Copyright © 2013 John Wiley & Sons, Ltd.     

The wake up and report problem is time-equivalent to the firing squad synchronization problem

We consider several problems relating to strongly-connected directed networks of identical finite-state processors that work synchronously in discrete time steps. The conceptually simplest of these problems is the Wake Up and Report Problem; this is the problem of having a unique root processor send a signal to all other processors in the network and then enter a special done state only when all other processors have received the signal. The most difficult of the problems we consider is the classic Firing Squad Synchronization Problem; this is the much-studied problem of achieving macro-synchronization in a network given micro-synchronization. We show via a complex algorithmic application of the snake data structure first introduced in Even, Litman, and Winkler [6] that these two problems in particular are asymptotically time-equivalent up to a constant factor. This result leads immediately to the inclusion of several other related problems into this new asymptotic time-class.Published online: 6 February 2004