A stronglypolynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique, called continuous scaling. The main measure of progress is that within a strongly...
详细信息
ISBN:
(纸本)9781450327107
A stronglypolynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique, called continuous scaling. The main measure of progress is that within a stronglypolynomial number of steps, an arc can be identified that must be tight in every dual optimal solution, and thus can be contracted.
Problems of statistical inference involve the adjustment of sample observations so they fit some a priori rank requirements, or order constraints. In such problems, the objective is to minimize the deviation cost func...
详细信息
Problems of statistical inference involve the adjustment of sample observations so they fit some a priori rank requirements, or order constraints. In such problems, the objective is to minimize the deviation cost function that depends on the distance between the observed value and the modify value. In Markov random field problems, there is also a pairwise relationship between the objects. The objective in Markov random field problem is to minimize the sum of the deviation cost function and a penalty function that grows with the distance between the values of related pairs-separation function. We discuss Markov random fields problems in the context of a representative application-the image segmentation problem. In this problem, the goal is to modify color shades assigned to pixels of an image so that the penalty function consisting of one term due to the deviation from the initial color shade and a second term that penalizes differences in assigned values to neighboring pixels is minimized. We present here an algorithm that solves the problem in polynomial time when the deviation function is convex and separation function is linear;and in stronglypolynomial time when the deviation cost function is linear, quadratic or piecewise linear convex with few pieces (where "few" means a number exponential in a polynomial function of the number of variables and constraints). The complexity of the algorithm for a problem on n pixels or variables, m adjacency relations or constraints, and range of variable values (colors) U, is O(T (n, m) + n log U) where T (n, m) is the complexity of solving the minimum s, t cut problem on a graph with n nodes and m arcs. Furthermore, other algorithms are shown to solve the problem with convex deviation and convex separation in running time O (mn log n log n U) and the problem with nonconvex deviation and convex separation in running time 0(T (n U, m U). The nonconvex separation problem is NP-hard even for fixed value of U. For the family of p
In this paper, we consider inverse maximum flow problem under the weighted Hamming distance. Four models are studied: the problem under sum-type weighted Hamming distance;the problem under bottleneck-type weighted Ham...
详细信息
In this paper, we consider inverse maximum flow problem under the weighted Hamming distance. Four models are studied: the problem under sum-type weighted Hamming distance;the problem under bottleneck-type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in stronglypolynomial times.
We present two efficient algorithms for the minimum-cost flow problem in which are costs are piecewise-linear and convex. Our algorithms are based on novel algorithms of Orlin, which were developed for the case of lin...
详细信息
We present two efficient algorithms for the minimum-cost flow problem in which are costs are piecewise-linear and convex. Our algorithms are based on novel algorithms of Orlin, which were developed for the case of linear are costs. Our first algorithm uses the Edmonds-Karp scaling technique. Its complexity is O(M log U(m + n log M)) for a network with n vertices, m arcs, M linear cost segments, and an upper bound U on the supplies and the capacities. The second algorithm is a stronglypolynomial version of the first, and it uses Tardos's idea of contraction. Its complexity is O(M log M(m + n log M)). Both algorithms improve by a factor of at least Mim the complexity of directly applying existing algorithms to a transformed network in which are costs are linear.
The inverse optimization problem is to modify the weight (or cost, length, capacity and so on) such that a given feasible solution becomes an optimal solution. In this paper, we consider the inverse min-max spanning t...
详细信息
The inverse optimization problem is to modify the weight (or cost, length, capacity and so on) such that a given feasible solution becomes an optimal solution. In this paper, we consider the inverse min-max spanning tree problem under the weighted sum-type Hamming distance. For the model considered, we present its combinatorial algorithm that runs in stronglypolynomial times. (C) 2007 Elsevier B.V. All rights reserved.
We prove a tight Theta(min(nm log(nC), nm(2))) bound on the number of iterations of the minimum-mean cycle-canceling algorithm of Goldberg and Tarjan [13]. We do this by giving the lower bound and by improving the str...
详细信息
We prove a tight Theta(min(nm log(nC), nm(2))) bound on the number of iterations of the minimum-mean cycle-canceling algorithm of Goldberg and Tarjan [13]. We do this by giving the lower bound and by improving the stronglypolynomial upper bound on the number of iterations to O(nm(2)). We also give an improved version of the maximum-mean cut canceling algorithm of [7], which is a dual of the minimum-mean cycle-canceling algorithm. Our version of the dual algorithm runs in O(nm(2)) iterations.
In an inverse combinatorial optimization problem, a feasible solution is given and is not optimal under the current parameters. The aim is to make the feasible solution optimal by modifying the current parameters as l...
详细信息
In an inverse combinatorial optimization problem, a feasible solution is given and is not optimal under the current parameters. The aim is to make the feasible solution optimal by modifying the current parameters as little as possible. The modification cost can be measured by different norms, such as weighted l(1) norm, weighted l(2) norm, weighted l(infinity) norm, weighted Hamming distance and so on. In this paper, we focus on the constrained inverse minimum flow problems under the weighted Hamming distance. Three different models are considered: the general problem under the weighted bottleneck-type Hamming distance and two cases under the mixed of sum-type and bottleneck type. strongly polynomial algorithms are presented for the models we studied. (C) 2021 Elsevier B.V. All rights reserved.
In this paper, we study the inverse problem of submodular functions on digraphs. Given a feasible solution x* for a linear program generated by a submodular function defined on digraphs, we try to modify the coefficie...
详细信息
In this paper, we study the inverse problem of submodular functions on digraphs. Given a feasible solution x* for a linear program generated by a submodular function defined on digraphs, we try to modify the coefficient vector c of the objective function, optimally and within bounds, such that x* becomes an optimal solution of the linear program. It is shown that the problem can be formulated as a combinatorial linear program and can be transformed further into a minimum cost circulation problem. Hence, it can be solved in stronglypolynomial time. We also give a necessary and sufficient condition for the feasibility of the problem. Finally, we extend the discussion to the version of the inverse problem with multiple feasible solutions.
In this paper, we consider the constrained inverse min-max spanning tree problems under the weighted Hamming distance. Three models are studied: the problem under the bottleneck-type weighted Hamming distance and two ...
详细信息
In this paper, we consider the constrained inverse min-max spanning tree problems under the weighted Hamming distance. Three models are studied: the problem under the bottleneck-type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in stronglypolynomial times.
In this paper, we first consider a network improvement problem, called vertex-to-vertices distance reduction problem. The problem is how to use a minimum cost to reduce lengths of the edges in a network so that the di...
详细信息
In this paper, we first consider a network improvement problem, called vertex-to-vertices distance reduction problem. The problem is how to use a minimum cost to reduce lengths of the edges in a network so that the distances from a given vertex to all other vertices are within a given upper bound. We use l(infinity), l(1) and l(2) norms to measure the total modification cost respectively. Under l(infinity) norm, we present a stronglypolynomial algorithm to solve the problem, and under l(1) or weighted l(2) norm, we show that achieving an approximation ratio O( log(|V|)) is NP-hard. We also extend the results to the vertex-to-points distance reduction problem, which is to reduce the lengths of edges most economically so that the distances from a given vertex to all points on the edges of the network are within a given upper bound.
暂无评论