A standard quadratic optimization problems (StQP) asks for the minimal value of a quadratic form over the standard simplex. StQPs form a central NP-hard class in quadratic optimization and have numerous practical appl...
详细信息
A standard quadratic optimization problems (StQP) asks for the minimal value of a quadratic form over the standard simplex. StQPs form a central NP-hard class in quadratic optimization and have numerous practical applications. In this note we study the case of a separable objective function and propose an algorithm of worst-case complexity . Some extensions to multi-StQPs and a"" (1)-ball constrained problems are also addressed briefly.
An instance of the classical Stable Roommates problem need not admit a stable matching. Previous work has considered the problem of finding a matching that is "as stable as possible", i.e., admits the minimu...
详细信息
An instance of the classical Stable Roommates problem need not admit a stable matching. Previous work has considered the problem of finding a matching that is "as stable as possible", i.e., admits the minimum number of blocking pairs. It is known that this problem is NP-hard and not approximable within n(1/2-epsilon), for any epsilon > 0, unless P = NP, where n is the number of agents in a given instance. In this paper, we extend the study to the Stable Roommates problem with Incomplete lists. In particular, we consider the case that the lengths of the lists are bounded by some integer d. We show that, even if d = 3, there is some c > 1 such that the problem of finding a matching with the minimum number of blocking pairs is not approximable within c unless P = NP. On the other hand, we show that the problem is solvable in polynomialtime ford <= 2, and we give a (2d - 3)-approximation algorithm for fixed d >= 3. If the given lists satisfy an additional condition (namely the absence of a so-called elitist odd party - a structure that is unlikely to exist in general), the performance guarantee improves to 2d - 4. (C) 2012 Elsevier B.V. All rights reserved.
Given an undirected graph and pairs of terminals the RESTRICTED VERTEX MULTICUT problem asks for a minimum set of nonterminal vertices whose removal disconnects each pair of terminals. The problem is known to be NP-co...
详细信息
Given an undirected graph and pairs of terminals the RESTRICTED VERTEX MULTICUT problem asks for a minimum set of nonterminal vertices whose removal disconnects each pair of terminals. The problem is known to be NP-complete for trees and polynomial-time solvable for interval graphs. In this paper we give a polynomial-time algorithm for the problem on permutation graphs. Furthermore we show that the problem remains NP-complete on split graphs whereas it becomes polynomial-time solvable for the class of co-bipartite graphs. (C) 2012 Elsevier B.V. All rights reserved.
The x-and-y-axes travelling salesman problem forms a special case of the Euclidean TSP, where all cities are situated on the x-axis and on the y-axis of an orthogonal coordinate system of the Euclidean plane. By caref...
详细信息
The x-and-y-axes travelling salesman problem forms a special case of the Euclidean TSP, where all cities are situated on the x-axis and on the y-axis of an orthogonal coordinate system of the Euclidean plane. By carefully analyzing the underlying combinatorial and geometric structures, we show that this problem can be solved in polynomialtime. The running time of the resulting algorithm is quadratic in the number of cities. (C) 2012 Elsevier By. All rights reserved.
The optimal power flow (OPF) problem is nonconvex and generally hard to solve. In this paper, we propose a semidefinite programming (SDP) optimization, which is the dual of an equivalent form of the OPF problem. A glo...
详细信息
The optimal power flow (OPF) problem is nonconvex and generally hard to solve. In this paper, we propose a semidefinite programming (SDP) optimization, which is the dual of an equivalent form of the OPF problem. A global optimum solution to the OPF problem can be retrieved from a solution of this convex dual problem whenever the duality gap is zero. A necessary and sufficient condition is provided in this paper to guarantee the existence of no duality gap for the OPF problem. This condition is satisfied by the standard IEEE benchmark systems with 14, 30, 57, 118, and 300 buses as well as several randomly generated systems. Since this condition is hard to study, a sufficient zero-duality-gap condition is also derived. This sufficient condition holds for IEEE systems after small resistance (10(-5) per unit) is added to every transformer that originally assumes zero resistance. We investigate this sufficient condition and justify that it holds widely in practice. The main underlying reason for the successful convexification of the OPF problem can be traced back to the modeling of transformers and transmission lines as well as the non-negativity of physical quantities such as resistance and inductance.
For an integer t and a Fixed graph H, we consider the problem of Finding a maximum t-matching not containing H as a subgraph, which we call the H-free t-matching problem. This problem is a generalization of the proble...
详细信息
For an integer t and a Fixed graph H, we consider the problem of Finding a maximum t-matching not containing H as a subgraph, which we call the H-free t-matching problem. This problem is a generalization of the problem of finding a maximum 2-matching with no short cycles, which has been well-studied as a natural relaxation of the Hamiltonian circuit problem. When H is a complete graph Kt+1 or a complete bipartite graph K-t,K-t, in 2010, Berczi and Vegh gave a polynomial-time algorithm for the H-free t-matching problem in simple graphs with maximum degree at most t + 1. A main contribution of this paper is to extend this result to the case when H is a t-regular complete partite graph. We also show that the problem is NP-complete when H is a connected t-regular graph that is not complete partite. Since it is known that, for a connected t-regular graph H, the degree sequences of all H-free t-matchings in a graph form a jump system if and only if H is a complete partite graph, our results show that the polynomial-time solvability of the H-free t-matching problem is consistent with this condition. (C) 2012 Elsevier B.V. All rights reserved.
The Eulerian closed walk problem in a digraph is a well-known polynomial-time solvable problem. In this paper, we show that if we impose the feasible solutions to fulfill some precedence constraints specified by paths...
详细信息
The Eulerian closed walk problem in a digraph is a well-known polynomial-time solvable problem. In this paper, we show that if we impose the feasible solutions to fulfill some precedence constraints specified by paths of the digraph, then the problem becomes NP-complete. We also present a polynomial-time algorithm to solve this variant of the Eulerian closed walk problem when the set of paths does not contain some forbidden structure. This allows us to give necessary and sufficient conditions for the existence of feasible solutions in this polynomial-time solvable case. (C) 2012 Published by Elsevier B.V.
This paper considers a minimum spanning tree problem under the situation where costs for constructing edges in a network include both fuzziness and randomness. In particular, this article focuses on the case that the ...
详细信息
This paper considers a minimum spanning tree problem under the situation where costs for constructing edges in a network include both fuzziness and randomness. In particular, this article focuses on the case that the edge costs are expressed by random fuzzy variables. A new decision making model based on a possibility measure and a value at risk measure is proposed in order to find a solution which fully reflects random and fuzzy information. It is shown that an optimal solution of the proposed model is obtained by a polynomial-time algorithm. (C) 2012 Elsevier Ltd. All rights reserved.
Given a preference system (G, <) and an integral weight function defined on the edge set of G (not necessarily bipartite), the maximum-weight stable matching problem is to find a stable matching of (G, <) with m...
详细信息
Given a preference system (G, <) and an integral weight function defined on the edge set of G (not necessarily bipartite), the maximum-weight stable matching problem is to find a stable matching of (G, <) with maximum total weight. In this paper we study this NP-hard problem using linear programming and polyhedral approaches. We show that the Rothblum system for defining the fractional stable matching polytope of (G, <) is totally dual integral if and only if this polytope is integral if and only if (G, <) has a bipartite representation. We also present a combinatorial polynomial-time algorithm for the maximum-weight stable matching problem and its dual on any preference system with a bipartite representation. Our results generalize Kiraly and Pap's theorem on the maximum-weight stable-marriage problem and rely heavily on their work.
A theorem is proved on the structure of the group of isometries of a Hermitian map b: V X V -> W, where V and W are vector spaces over a finite field of odd order. Also a Las Vegas polynomial-time algorithm is pres...
详细信息
A theorem is proved on the structure of the group of isometries of a Hermitian map b: V X V -> W, where V and W are vector spaces over a finite field of odd order. Also a Las Vegas polynomial-time algorithm is presented which, given a Hermitian map, finds generators for, and determines the structure of its isometry group. The algorithm can be adapted to construct the intersection over a set of classical subgroups of GL(V), giving rise to the first polynomial-time solution of this old problem. The approach yields new algorithmic tools for algebras with involution, which in turn have applications to other computational problems of interest. Implementations of the various algorithms in the MAGMA system demonstrate their practicability.
暂无评论