Let C be a full-dimensional pointed closed convex cone in R-m obtained by taking the conic hull of a strictly convex set. Given A is an element of Q(mxn1), B is an element of Q(mxn2), and b is an element of Q(m), a si...
详细信息
Let C be a full-dimensional pointed closed convex cone in R-m obtained by taking the conic hull of a strictly convex set. Given A is an element of Q(mxn1), B is an element of Q(mxn2), and b is an element of Q(m), a simple conic mixed-integer set (SCMIS) is a set of the form {(x, y) is an element of Z(n1) x R-n2 vertical bar Ax + By - b is an element of C}. In this paper, we give a complete characterization of the closedness of convex hulls of SCMISs. Under certain technical conditions on the cone C, we show that the closedness characterization can be used to construct a polynomial-time algorithm to check the closedness of convex hulls of SCMISs. Moreover, we also show that the Lorentz cone satisfies these technical conditions. In the special case of pure integer problems, we present sufficient conditions, which can be checked in polynomialtime, to verify the closedness of intersection of SCMISs.
This paper investigates the anchor points in nonconvex Data Envelopment Analysis (DEA), called Free Disposal Hull (FDH), technologies. We develop the concept of anchor points under various returns to scale as-sumption...
详细信息
This paper investigates the anchor points in nonconvex Data Envelopment Analysis (DEA), called Free Disposal Hull (FDH), technologies. We develop the concept of anchor points under various returns to scale as-sumptions in FDH models. A necessary and sufficient condition for characterizing the anchor points is provided. Since the set of anchor points is a subset of the set of extreme units, a definition of extreme units in non-convex technologies as well as a new method for obtaining these units are given. Finally, a polynomial-time algorithm for identification of the anchor points in FDH models is provided. Obtaining both extreme units and anchor points is done via calculating only some ratios, without solving any mathematical programming problem. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.
This study concerns joint channel and power allocation scheme for multi-user orthogonal frequency division multiple access system. The author's highlight is margin adaptive (MA) resource allocation problem namely ...
详细信息
This study concerns joint channel and power allocation scheme for multi-user orthogonal frequency division multiple access system. The author's highlight is margin adaptive (MA) resource allocation problem namely minimising the total transmit power of users with rate requirement constraints. MA is generally provable NP-hard;the typical methods are either to relax and round, or to fix the transmission mode of users (e.g. modulation and coding). Differently, they reorganise MA problem with only power variables left and design a novel relaxation scheme to enable the convexity. The polynomial-time algorithm-interior-point method-is employed to solve the relaxation problem and the theoretical complexity is further presented. Simulation results demonstrate that the author's scheme can provide high energy efficiency compared with the existing methods, 100% relative error bounds with respect to the optimum in most cases, and low computational complexity.
In the two disjoint shortest paths problem (2-DSPP), the input is a graph (or a digraph) and its vertex pairs (s(1), t(1)) and (S-2, t(2)), and the objective is to find two vertex-disjoint paths P-1 and P-2 such that ...
详细信息
In the two disjoint shortest paths problem (2-DSPP), the input is a graph (or a digraph) and its vertex pairs (s(1), t(1)) and (S-2, t(2)), and the objective is to find two vertex-disjoint paths P-1 and P-2 such that P-i is a shortest path from s(i) to t(i) for i = 1, 2, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function. (C) 2018 Elsevier B.V. All rights reserved.
The problem of counting the number of cuts with the minimum cardinality in an undirected multigraph arises in various applications such as testing the super-lambda-ness of a graph and calculating upper and lower bound...
详细信息
The problem of counting the number of cuts with the minimum cardinality in an undirected multigraph arises in various applications such as testing the super-lambda-ness of a graph and calculating upper and lower bounds on the probabilistic connectedness of a stochastic graph G in which edges are subject to failure. This paper shows that the number \C(G)\ of cuts with the minimum cardinality lambda(G) in a multiple graph G = (V, E) can be computed in O(\E\ + lambda(G)\V\2 + lambda(G)\C(G) parallel-to V\) time.
The bipartization problem for a graph G asks for finding a subset S of V(G) such that the induced subgraph G[S] is bipartite and vertical bar S vertical bar is maximized. This problem has significant applications in t...
详细信息
The bipartization problem for a graph G asks for finding a subset S of V(G) such that the induced subgraph G[S] is bipartite and vertical bar S vertical bar is maximized. This problem has significant applications in the via minimization of VLSI design. The problem has been proved NP-complete and the fixed parameter solvability has been known in the literature. This paper presents several polynomial-time algorithms for special graph families, such as split graphs, co-bipartite graphs, chordal graphs, and permutation graphs.
We consider the concepts of a t-total vertex cover and a t-total edge cover (t >= 1), which generalise the notions of a vertex cover and an edge cover, respectively. A t-total vertex (respectively edge) cover of a ...
详细信息
We consider the concepts of a t-total vertex cover and a t-total edge cover (t >= 1), which generalise the notions of a vertex cover and an edge cover, respectively. A t-total vertex (respectively edge) cover of a connected graph G is a vertex (edge) cover S of G such that each connected component of the subgraph of G induced by S has at least t vertices (edges). These definitions are motivated by combining the concepts of clustering and covering in graphs. Moreover they yield a spectrum of parameters that essentially range from a vertex cover to a connected vertex cover (in the vertex case) and from an edge cover to a spanning tree (in the edge case). For various values of t, we present NP-completeness and approximability results (both upper and lower bounds) and FPT algorithms for problems concerned with finding the minimum size of a t-total vertex cover, t-total edge cover and connected vertex cover, in particular improving on a previous FPT algorithm for the latter problem. (C) 2008 Elsevier B. V. All rights reserved.
A heuristic algorithm is developed for finding the maximum independent set of vertices in an undirected graph. To this end, the technique of finite partially ordered sets is used, in particular, the technique of parti...
详细信息
A heuristic algorithm is developed for finding the maximum independent set of vertices in an undirected graph. To this end, the technique of finite partially ordered sets is used, in particular, the technique of partitioning such a set into a minimum number of chains. A special digraph is constructed and a solution algorithm is proposed on the basis of a hypothesis about its properties. Some experimental data are presented for well-known examples.
For every string inclusion relation there are two optimization problems: find a longest string included in every string of a given finite language, and find a shortest string including every string of a given finite l...
详细信息
For every string inclusion relation there are two optimization problems: find a longest string included in every string of a given finite language, and find a shortest string including every string of a given finite language. As an example, the two well-known pairs of problems, the longest common substring (or subsequence) problem and the shortest common superstring (or supersequence) problem, are interpretations of these two problems. In this paper we consider a class of opposite problems connected with string noninclusion relations: find a shortest string included in no string of a given finite language and find a longest string including no string of a given finite language. The predicate "string alpha is not included in string beta" is interpreted as either "alpha is not a substring of beta" or "alpha is not a subsequence of beta". The main purpose is to determine the complexity status of the string noninclusion optimization problems. Using graph approaches we present polynomial-time algorithms for the first interpretation and NP-hardness proofs for the second. We also discuss restricted versions of the problems, correlations between the string inclusion and noninclusion problems, and generalized problems which are the string inclusion problems for one language and the string noninclusion problems for another. In applications the string inclusion problems are used to find a similarity between any structures which can be represented by strings. Respectively, the noninclusion problems can be used to find a nonsimilarity. Such problems occur in computational molecular biology, data compression, pattern recognition, and flexible manufacturing. The above generalized problems arise naturally in all of these applied areas. Apart from this practical reason, we hope that studying the string noninclusion problems will yield deeper understanding of the string inclusion problems.
We propose a new polynomial-time deterministic algorithm that produces an approximated solution for the travelling salesperson problem. The proposed algorithm ranks cities based on their priorities calculated using a ...
详细信息
We propose a new polynomial-time deterministic algorithm that produces an approximated solution for the travelling salesperson problem. The proposed algorithm ranks cities based on their priorities calculated using a power function of means and standard deviations of their distances from other cities and then connects the cities to their neighbours in the order of their priorities. When connecting a city, a neighbour is selected based on their neighbours' priorities calculated as another power function that additionally includes their distance from the focal city to be connected. This repeats until all the cities are connected into a single loop. The time complexity of the proposed algorithm is O(n(2)), where n is the number of cities. Numerical evaluation shows that, despite its simplicity, the proposed algorithm produces shorter tours with less time complexity than other conventional tour construction heuristics. The proposed algorithm can be used by itself or as an initial tour generator for other more complex heuristic optimisation algorithms.
暂无评论