Improved Approximation Algorithm for Convex Recoloring of Trees

A pair (T,C) of a tree T and a coloring C is called a colored tree. Given a colored tree (T,C) any coloring C′ of T is called a recoloring of T. Given a weight function on the vertices of the tree the recoloring distance of a recoloring is the total weight of recolored vertices. A coloring of a tree is convex if for any two vertices u and v that are colored by the same color c, every vertex on the path from u to v is also colored by c. In the minimum convex recoloring problem we are given a colored tree and a weight function and our goal is to find a convex recoloring of minimum recoloring distance. The minimum convex recoloring problem naturally arises in the context of phylogenetic trees. Given a set of related species the goal of phylogenetic reconstruction is to construct a tree that would best describe the evolution of this set of species. In this context a convex coloring corresponds to perfect phylogeny. Since perfect phylogeny is not always possible the next best thing is to find a tree which is as close to convex as possible, or, in other words, a tree with minimum recoloring distance. We present a (2+ε)-approximation algorithm for the minimum convex recoloring problem, whose running time is O(n ²+n(1/ε)²4^1/ε ). This result improves the previously known 3-approximation algorithm for this NP-hard problem. We also present an algorithm for computing an optimal convex recoloring whose running time is , where n ^* is the number of colors that violate convexity in the input tree, and Δ is the maximum degree of vertices in the tree. The parameterized complexity of this algorithm is O(n ²+n⋅k⋅2 ^k ).     

Quasi-Lagrangian Neural Network for Convex Quadratic Optimization

A new neural network for convex quadratic optimization is presented in this brief. The proposed network can handle both equality and inequality constraints, as well as bound constraints on the optimization variables. It is based on the Lagrangian approach, but exploits a partial dual method in order to keep the number of variables at minimum. The dynamic evolution is globally convergent and the steady-state solutions satisfy the necessary and sufficient conditions of optimality. The circuit implementation is simpler with respect to existing solutions for the same class of problems. The validity of the proposed approach is verified through some simulation examples.     

Designing Camera Networks by Convex Quadratic Programming

In this paper, we study the problem of automatic camera placement for computer graphics and computer vision applications. We extend the problem formulations of previous work by proposing a novel way to incorporate visibility constraints and camera‐to‐camera relationships. For example, the placement solution can be encouraged to have cameras that image the same important locations from different viewing directions, which can enable reconstruction and surveillance tasks to perform better. We show that the general camera placement problem can be formulated mathematically as a convex binary quadratic program (BQP) under linear constraints. Moreover, we propose an optimization strategy with a favorable trade‐off between speed and solution quality. Our solution is almost as fast as a greedy treatment of the problem, but the quality is significantly higher, so much so that it is comparable to exact solutions that take orders of magnitude more computation time. Because it is computationally attractive, our method also allows users to explore the space of solutions for variations in input parameters. To evaluate its effectiveness, we show a range of 3D results on real‐world floorplans (garage, hotel, mall, and airport).     

H2/ l1 混合优化问题的凸二次规划解法

采用上逼近算法求解H1/l1混合优化问题,首先将其转化为有限维的凸二次规划问题,并利用Lemke互补转轴算法求解;然后逐次进行逼近,计算请示例表明所得结果是正确的。     

A Multi-criteria Convex Quadratic Programming model for credit data analysis

Speed and scalability are two essential issues in data mining and knowledge discovery. This paper proposed a mathematical programming model that addresses these two issues and applied the model to Credit Classification Problems. The proposed Multi-criteria Convex Quadric Programming (MCQP) model is highly efficient (computing time complexity O(n^1.5–2)) and scalable to massive problems (size of O(10⁹)) because it only needs to solve linear equations to find the global optimal solution. Kernel functions were introduced to the model to solve nonlinear problems. In addition, the theoretical relationship between the proposed MCQP model and SVM was discussed.     

Learning Natural Colors for Image Recoloring

We present a data‐driven method for automatically recoloring a photo to enhance its appearance or change a viewer's emotional response to it. A compact representation called a RegionNet summarizes color and geometric features of image regions, and geometric relationships between them. Correlations between color property distributions and geometric features of regions are learned from a database of well‐colored photos. A probabilistic factor graph model is used to summarize distributions of color properties and generate an overall probability distribution for color suggestions. Given a new input image, we can generate multiple recolored results which unlike previous automatic results, are both natural and artistic, and compatible with their spatial arrangements.     

Crown Structures for Vertex Cover Kernelization

Crown structures in a graph are defined and shown to be useful in kernelization algorithms for the classic vertex cover problem. Two vertex cover kernelization methods are discussed. One, based on linear programming, has been in prior use and is known to produce predictable results, although it was not previously associated with crowns. The second, based on crown structures, is newer and much faster, but produces somewhat variable results. These two methods are studied and compared both theoretically and experimentally with each other and with older, more primitive kernelization algorithms. Properties of crowns and methods for identifying them are discussed. Logical connections between linear programming and crown reductions are established. It is shown that the problem of finding an induced crown-free subgraph, and the problem of finding a crown of maximum size in an arbitrary graph, are solvable in polynomial time.     

积分二次约束下系统鲁棒镇定的凸参数化方法

研究了积分二次约束下不确定系统的鲁棒控制器设计问题. 通过将控制器的Youla参数化方法与鲁棒稳定性频域判据相结合, 将鲁棒控制器设计问题转化为RH∞空间的凸可行性问题, 进而将该问题转化为求解频域线性矩阵不等式的可行解问题. 在此基础上, 利用有理函数矩阵边界插值方法求得鲁棒控制器.     

H_2/l_1混合优化问题的凸二次规划解法

采用上逼近算法求解 H2 / l1 混合优化问题。首先将其转化为有限维的凸二次规划问题 ,并利用L emke互补转轴算法求解 ;然后逐次进行逼近。计算示例表明所得结果是正确的     

加权3-Set Packing问题的核心化

Packing和Matching问题是一类重要的NP难解问题,该类问题的参数算法和核心化研究受到了人们广泛的关注.主要研究了加权3-SetPacking的核心化算法.对于加权3-SetPacking问题,基于对问题结构的深入分析,提出并证明了2个简化规则.首先限定加权3-SetPacking问题实例中包含给定2个元素的集合的个数,然后在限定问题实例中包含1个给定元素的集合的个数.基于对集合个数的限定,得到问题实例中总的集合个数的上界.并基于上述性质得到2个简化规则,可得到加权3-SetPacking问题大小为27k3-36k2+12k的核,该核心化结果是加权3-SetPacking问题的首个核心化结果.得到的加权3-SetPacking的核心化过程同样适用于加权3D-Matching问题的核化,可得到与加权3-SetPacking问题同样大小的问题核.     

Relaxed Stability Criteria for Time-Delay Systems:A Novel Quadratic Function Convex Approximation Approach

This paper develops a quadratic function convex approximation approach to deal with the negative definite problem of the quadratic function induced by stability analysis of linear systems with time-varying delays. By introducing two adjustable parameters and two free variables, a novel convex function greater than or equal to the quadratic function is constructed, regardless of the sign of the coefficient in the quadratic term. The developed lemma can also be degenerated into the existing quadra...     

Towards Optimal and Expressive Kernelization for d-Hitting Set

A sunflower in a hypergraph is a set of hyperedges pairwise intersecting in exactly the same vertex set. Sunflowers are a useful tool in polynomial-time data reduction for problems formalizable as d-Hitting Set, the problem of covering all hyperedges (whose cardinality is bounded from above by a constant d) of a hypergraph by at most k vertices. Additionally, in fault diagnosis, sunflowers yield concise explanations for “highly defective structures”. We provide a linear-time algorithm that, by finding sunflowers, transforms an instance of d-Hitting Set into an equivalent instance comprising at most O(k ^d ) hyperedges and vertices. In terms of parameterized complexity, we show a problem kernel with asymptotically optimal size (unless \(\operatorname {coNP}\subseteq \operatorname {NP/poly}\) ) and provide experimental results that show the practical applicability of our algorithm. Finally, we show that the number of vertices can be reduced to O(k ^d?1) with additional processing in O(k ^1.5d ) time—nontrivially combining the sunflower technique with problem kernels due to Abu-Khzam and Moser.     

Convex formulations for optimal selection of controlled variables and measurements using Mixed Integer Quadratic Programming

The appropriate selection of controlled variables is important for operating a process optimally in the presence of disturbances. Self-optimizing control provides a mathematical framework for selecting the controlled variables as combinations of measurements, c = Hy, with the aim to minimize the steady state loss from optimal operation. In this paper, we present (i) a convex formulation to find the optimal combination matrix H for a given measurement set and (ii) a Mixed-Integer Quadratic Programming (MIQP) methodology to select optimal measurement subsets that result in minimal loss. The methods presented in this paper are exact for quadratic problems with linear measurement relations. The MIQP methods can handle additional structural constraints compared to the branch and bound (BAB) methods reported in literature. The MIQP methods are evaluated on a toy test problem, an evaporator example, a binary distillation column example with 41 stages and a Kaibel column with 71 stages.     

顶点覆盖问题线性内核算法

参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).     

Continuous Time Linear Quadratic Regulator With Control Constraints via Convex Duality

A continuous time infinite horizon linear quadratic regulator with input constraints is studied. Optimality conditions, both in the open loop and feedback form, and continuity and differentiability properties of the optimal value function and of the optimal feedback are shown. Arguments rely on basic ideas of convex conjugacy, and in particular, use a dual optimal control problem     

Quadratic Stabilization of Switched Uncertain Linear Systems: A Convex Combination Approach

We consider quadratic stabilization for a class of switched systems which are composed of a finite set of continuoustime linear subsystems with norm bounded uncertainties. Under the assumption that there is no single quadratically stable subsystem, if a convex combination of subsystems is quadratically stable, then we propose a state-dependent switching law, based on the convex combination of subsystems, such that the entire switched linear system is quadratically stable. When the state information is not available, we extend the discussion to designing an output-dependent switching law by constructing a robust Luenberger observer for each subsystem.      

Interval Uncertainty-Based Robust Optimization for Convex and Non-Convex Quadratic Programs with Applications in Network Infrastructure Planning

Planning infrastructure networks such as roads, pipelines, waterways, power lines and telecommunication systems, require estimations on the future demand as well as other uncertain factors such as operating costs, degradation rates, or the like. When trying to construct infrastructure that is either optimal from a social welfare or profit perspective (depending on a public or private sector focus), typically researchers treat the uncertainties in the problem by using robust optimization methods. The goal of robust optimization is to find optimal solutions that are relatively insensitive to uncertain factors. This paper presents an efficient and tractable approach for finding robust optimum solutions to linear and, more importantly, quadratic programming problems with interval uncertainty using a worst case analysis. For linear, mixed-integer linear, and mixed-integer problems with quadratic objective and constraint functions, our robust formulations have the same complexity and tractability as their deterministic counterparts. Numerous examples with differing difficulties and complexities, especially with selected ones on network planning/operations problems, have been tested to demonstrate the viability of the proposed approach. The results show that the computational effort of the proposed approach, in terms of the number of function calls, for the robust problems is comparable to or even better than that of deterministic problems in some cases.     

最多叶子生成树问题的核化算法

对算法领域的最多叶子生成树问题进行了深入研究,提出了对简单连通图2度节点的化简规则,并证明了不含2度节点的图的生成树的叶子节点数的下限为(N+6)/4,给出了构造这样一棵生成树的构造性方法.基于上述化简规则和所证明的结论,给出了最多叶子生成树问题的核化算法,该核化算法可以在O(n2)时间内得到一个4k-6大小的线性核.对于这样一个较小的核,将大大提高相关的参数算法和近似算法的性能.