排序方式: 共有24条查询结果,搜索用时 62 毫秒
1.
We show that for any optimal solution
for a given separable quadratic integer programming problem there exist an optimal solution
for its continuous relaxation such that
wheren is the number of variables and(A) is the largest absolute subdeterminant of the integer constraint matrixA. Also for any feasible solutionz, which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution
having greater objective function value and with
. We further prove, under some additional assumptions, that the distance between a pair of optimal solutions to an integer quadratic programming problem with right hand side vectorsb andb, respectively, depends linearly on b–b1. Finally the validity of all the results for nonseparable mixed-integer quadratic programs is established. The proximity results obtained in this paper are extensions of some of the results described in Cook et al. (1986) for linear integer programming.This research was partially supported by Natural Sciences and Engineering Research Council of Canada Grant 5-83998. 相似文献
2.
3.
4.
5.
In this paper we study the maximum two-flow problem in vertex- and edge-capacitated undirected ST2-planar graphs, that is, planar graphs where the vertices of each terminal pair are on the same face. For such graphs we provide an O(n) algorithm for finding a minimum two-cut and an O(n log n) algorithm for determining a maximum two-flow and show that the value of a maximum two-flow equals the value of a minimum two-cut. We further show that the flow obtained is half-integral and provide a characterization of edge and vertex capacitated ST2-planar graphs that guarantees a maximum two-flow that is integral. By a simple variation of our maximum two-flow algorithm we then develop, for ST2-planar graphs with vertex and edge capacities, an O(n log n) algorithm for determining an integral maximum two-flow of value not less than the value of a maximum two-flow minus one. 相似文献
6.
Thomas W. Bell Albert Firestone Frieda Guzzo Lain-Yen Hu 《Journal of inclusion phenomena and macrocyclic chemistry》1987,5(2):149-152
A series of macrocyclic ligands related to hexaaza[18]-annulene form stable complexes with alkali metal and alkaline earth ions. A planar, substituent-solubilized torand, consisting of multiply fused pyridine rings, has been synthesized and has been found to sequester calcium from a dilute source. 相似文献
7.
8.
Frieda Granot S. Thomas McCormick Maurice Queyranne Fabio Tardella 《Mathematical Programming》2012,135(1-2):337-367
We consider the minimum s, t-cut problem in a network with parametrized arc capacities. Following the seminal work of Gallo et?al. (SIAM J. Comput. 18(1):30–55, 1989), classes of this parametric problem have been shown to enjoy the nice Structural Property that minimum cuts are nested, and the nice Algorithmic Property that all minimum cuts can be computed in the same asymptotic time as a single minimum cut by using a clever Flow Update step to move from one value of the parameter to the next. We present a general framework for parametric minimum cuts that extends and unifies such results. We define two conditions on parametrized arc capacities that are necessary and sufficient for (strictly) decreasing differences of the parametric cut function. Known results in parametric submodular optimization then imply the Structural Property. We show how to construct appropriate Flow Updates in linear time under the above conditions, implying that the Algorithmic Property also holds under these conditions. We then consider other classes of parametric minimum cut problems, without decreasing differences, for which we establish the Structural and/or the Algorithmic Property, as well as other cases where nested minimum cuts arise. 相似文献
9.
10.