Convex relaxation for a 3D spatiotemporal segmentation model using the primal-dual method

A method based on 3D videos is proposed for multi-target segmentation and tracking with a moving viewing system. A spatiotemporal energy functional is built up to perform motion segmentation and estimation simultaneously. To overcome the limitation of the local minimum problem with the level set method, a convex relaxation method is applied to the 3D spatiotemporal segmentation model. The relaxed convex model is independent of the initial condition. A primal-dual algorithm is used to improve computational efficiency. Several indoor experiments show the validity of the proposed method.     

Path Hitting in Acyclic Graphs

An instance of the path hitting problem consists of two families of paths, and ℋ, in a common undirected graph, where each path in ℋ is associated with a non-negative cost. We refer to and ℋ as the sets of demand and hitting paths, respectively. When p∈ℋ and share at least one mutual edge, we say that p hits q. The objective is to find a minimum cost subset of ℋ whose members collectively hit those of . In this paper we provide constant factor approximation algorithms for path hitting, confined to instances in which the underlying graph is a tree, a spider, or a star. Although such restricted settings may appear to be very simple, we demonstrate that they still capture some of the most basic covering problems in graphs. Our approach combines several novel ideas: We extend the algorithm of Garg, Vazirani and Yannakakis (Algorithmica, 18:3–20, 1997) for approximate multicuts and multicommodity flows in trees to prove new integrality properties; we present a reduction that involves multiple calls to this extended algorithm; and we introduce a polynomial-time solvable variant of the edge cover problem, which may be of independent interest. An extended abstract of this paper appeared in Proceedings of the 14th Annual European Symposium on Algorithms, 2006. This work is part of D. Segev’s Ph.D. thesis prepared at Tel-Aviv University under the supervision of Prof. Refael Hassin.     

Using the primal-dual interior point algorithm within the branch-price-and-cut method

Branch-price-and-cut has proven to be a powerful method for solving integer programming problems. It combines decomposition techniques with the generation of both columns and valid inequalities and relies on strong bounds to guide the search in the branch-and-bound tree. In this paper, we present how to improve the performance of a branch-price-and-cut method by using the primal-dual interior point algorithm. We discuss in detail how to deal with the challenges of using the interior point algorithm with the core components of the branch-price-and-cut method. The effort to overcome the difficulties pays off in a number of advantageous features offered by the new approach. We present the computational results of solving well-known instances of the vehicle routing problem with time windows, a challenging integer programming problem. The results indicate that the proposed approach delivers the best overall performance when compared with a similar branch-price-and-cut method which is based on the simplex algorithm.     

Primal-dual approximation algorithms for the Prize-Collecting Steiner Tree Problem

The primal-dual scheme has been used to provide approximation algorithms for many problems. Goemans and Williamson gave a (2−1/(n−1))-approximation for the Prize-Collecting Steiner Tree Problem that runs in O(n³logn) time—it applies the primal-dual scheme once for each of the n vertices of the graph. We present a primal-dual algorithm that runs in O(n²logn), as it applies this scheme only once, and achieves the slightly better ratio of (2−2/n). We also show a tight example for the analysis of the algorithm and discuss briefly a couple of other algorithms described in the literature.     

考虑暂态稳定约束的可用功率交换能力计算的研究

建立了计及暂态稳定约束的计算电力系统可用功率交换能力(ATC)的数学模型,采用转子角约束作为暂态稳定约束,利用梯形法将表示暂态稳定约束的微分方程离散化为差分方程,从而将这一问题转化为只含有代数约束方程的非线性规划问题,并利用高效的原一对偶内点法求解。7节点和36节点系统的计算结果表明了本所建立模型及所用方法的有效性。     

大规模电力系统无功优化问题的线性规划实用化算法

以原对偶内点法为基础,将信赖域思想引入线性规划算法,从而克服动态调整步长的困难。此外,采用三角分解法解修正方程,提高了计算速度。通过对一个实际的538节点系统进行数值计算,验证所提算法的有效性。     

An approximation algorithm for minimum-cost vertex-connectivity problems

We present an approximation algorithm for solving graph problems in which a low-cost set of edges must be selected that has certain vertex-connectivity properties. In the survivable network design problem, a valuer _ij for each pair of verticesi andj is given, and a minimum-cost set of edges such that there arer _ij vertex-disjoint paths between verticesi andj must be found. In the case for whichr _ij ∈{0, 1, 2} for alli, j, we can find a solution of cost no more than three times the optimal cost in polynomial time. In the case in whichr _ij =k for alli, j, we can find a solution of cost no more than 2H(k) times optimal, where . No approximation algorithms were previously known for these problems. Our algorithms rely on a primal-dual approach which has recently led to approximation algorithms for many edge-connectivity problems. This research was supported by NSF Grant CCR-91-03937 and a DIMACS postdoctoral fellowship, and was conducted in part while the author was visiting MIT. This research was supported by an NSF Graduate Fellowship and an NSF Postdoctoral Fellowship, and was conducted in part while the author was a graduate student at MIT and in part while a postdoc at Cornell.     

一种OCT 图像去噪的原始- 对偶算法

本文针对OCT图像噪声的特点,考虑一般的鞍点结构,提出一种原始-对偶算法,对OCT图像进行降噪处理。在对散斑噪声模型取对数处理之后,结合加性噪声的特点,采用原始-对偶结构提出算法,运算较为简单,容易编程实现,文中实验与均值滤波、半软阈值方法进行比较,结果表明,该算法在有效去除噪声的同时较好地保留了OCT图像中的重要细节信息,使图像的细节部分清晰。该算法可有效地去除OCT图像散斑噪声,提高图像的质量,同时文章建立的一般模型可推广到图像分割、目标识别和运动估计等图像处理领域。     

原始—对偶单纯形算法

原始——对偶单纯形算法是解线性规划问题的一种有效算法.它比原始单纯形法、两阶段单纯形法、对偶单纯形法具有更大的优越性.本文扼要介绍了原始——对偶单纯形算法及其数学模型,算法步骤和框图,并给出了算例.     

Elementary approximation algorithms for prize collecting Steiner tree problems

This paper deals with approximation algorithms for the prize collecting generalized Steiner forest problem, defined as follows. The input is an undirected graph G=(V,E), a collection T={T₁,…,T_k}, each a subset of V of size at least 2, a weight function , and a penalty function . The goal is to find a forest F that minimizes the cost of the edges of F plus the penalties paid for subsets T_i whose vertices are not all connected by F. Our main result is a -approximation for the prize collecting generalized Steiner forest problem, where n2 is the number of vertices in the graph. This obviously implies the same approximation for the special case called the prize collecting Steiner forest problem (all subsets T_i are of size 2). The approximation algorithm is obtained by applying the local ratio method, and is much simpler than the best known combinatorial algorithm for this problem.Our approach gives a -approximation for the prize collecting Steiner tree problem (all subsets T_i are of size 2 and there is some root vertex r that belongs to all of them). This latter algorithm is in fact the local ratio version of the primal-dual algorithm of Goemans and Williamson [M.X. Goemans, D.P. Williamson, A general approximation technique for constrained forest problems, SIAM Journal on Computing 24 (2) (April 1995) 296–317]. Another special case of our main algorithm is Bar-Yehuda's local ratio -approximation for the generalized Steiner forest problem (all the penalties are infinity) [R. Bar-Yehuda, One for the price of two: a unified approach for approximating covering problems, Algorithmica 27 (2) (June 2000) 131–144]. Thus, an important contribution of this paper is in providing a natural generalization of the framework presented by Goemans and Williamson, and later by Bar-Yehuda.