首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 140 毫秒
1.
In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions, we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent nonsmooth equation H(u,x)=0, where H:ℜ 2n →ℜ 2n , u∈ℜ n is a parameter variable and x∈ℜ n is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z k =(u k ,x k )} such that the mapping H(·) is continuously differentiable at each z k and may be non-differentiable at the limiting point of {z k }. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the proposed methods for particularly chosen smoothing functions are very promising. Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999  相似文献   

2.
S. Mishra  S.B. Rao 《Discrete Mathematics》2006,306(14):1586-1594
In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set SV, such that, for each uV, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.  相似文献   

3.
For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n k-1 F(n,m))=O(mn k log(n 2 /m)) time and O(n 2) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn 3) for weighted graphs, but improves the bound ?(mn 3) to O(n 2 F(n,m))=O(min{mn 8/3,m 3/2 n 2}) for unweighted graphs. The bound ?(mn 4) for k=4 improves the previous best randomized bound ?(n 6) (for m=o(n 2)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. Received: April 1999 / Accepted: February 2000?Published online August 18, 2000  相似文献   

4.
 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a uv shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,vS. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤lkn−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000  相似文献   

5.
The standard quadratic program (QPS) is minxεΔxTQx, where is the simplex Δ = {x ⩽ 0 ∣ ∑i=1n xi = 1}. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One class of ‘d.c.’ (for ‘difference between convex’) bounds for QPS is based on writing Q=ST, where S and T are both positive semidefinite, and bounding xT Sx (convex on Δ) and −xTx (concave on Δ) separately. We show that the maximum possible such bound can be obtained by solving a semidefinite programming (SDP) problem. The dual of this SDP problem corresponds to adding a simple constraint to the well-known Shor relaxation of QPS. We show that the max d.c. bound is dominated by another known bound based on a copositive relaxation of QPS, also obtainable via SDP at comparable computational expense. We also discuss extensions of the d.c. bound to more general quadratic programming problems. For the application of QPS to bounding the stability number of a graph, we use a novel formulation of the Lovasz ϑ number to compare ϑ, Schrijver’s ϑ′, and the max d.c. bound.  相似文献   

6.
We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume that for any submodular function f: ?→R on a distributive lattice ?⊆2 V with ?,V∈? and f(?)=0 and for any vector xR V where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|2) times, the descent method finds a sequence of subsets Z 1,Z 2,···,Z k of V such that f(Z 1)>f(Z 2)>···>f(Z k )=min{f(Y) | Y∈?}, where k is O(|V|2). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient membership algorithms. Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001  相似文献   

7.
We consider the MAX k‐CUT problem on random graphs Gn,p. First, we bound the probable weight of a MAX k‐CUT using probabilistic counting arguments and by analyzing a simple greedy heuristic. Then, we give an algorithm that approximates MAX k‐CUT in expected polynomial time, with approximation ratio 1 + O((np)‐1/2). Our main technical tool is a new bound on the probable value of Frieze and Jerrum's semidefinite programming (SDP)‐relaxation of MAX k‐CUT on random graphs. To obtain this bound, we show that the value of the SDP is tightly concentrated. As a further application of our bound on the probable value of the SDP, we obtain an algorithm for approximating the chromatic number of Gn,p, 1/np ≤ 0.99, within a factor of O((np)1/2) in polynomial expected time, thereby answering a question of Krivelevich and Vu. We give similar algorithms for random regular graphs. The techniques for studying the SDP apply to a variety of SDP relaxations of further NP‐hard problems on random structures and may therefore be of independent interest. For instance, to bound the SDP we estimate the eigenvalues of random graphs with given degree sequences. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006  相似文献   

8.
Given a directed graph G and an edge weight function w : A(G)→ R^ , the maximum directed cut problem (MAX DICUT) is that of finding a directed cut δ(S) with maximum total weight. We consider a version of MAX DICUT -- MAX DICUT with given sizes of parts or MAX DICUT WITH GSP -- whose instance is that of MAX DICUT plus a positive integer k, and it is required to find a directed cut δ(S) having maximum weight over all cuts δ(S) with |S| -- k. We present an approximation algorithm for this problem which is based on semidefinite programming (SDP) relaxation. The algorithm achieves the presently best performance guarantee for a range of k.  相似文献   

9.
We consider a Neumann problem of the type -εΔu+F (u(x))=0 in an open bounded subset Ω of R n , where F is a real function which has exactly k maximum points. Using Morse theory we find that, for ε suitably small, there are at least 2k nontrivial solutions of the problem and we give some qualitative information about them. Received: October 30, 1999 Published online: December 19, 2001  相似文献   

10.
We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with k=1 and k=2, every optimal solution is integral. In contrast to this, for every k≥3 there exist instances where every optimal solution takes non-integral values. Received: August 2001 / Accepted: January 2002?Published online March 27, 2002  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号