共查询到20条相似文献,搜索用时 15 毫秒
1.
LetM
1 andM
2 be matroids onS,B be theirk-element common independent set, andw a weight function onS. Given two functionsb 0 andc 0 onS, the Inverse Matroid Intersection Problem (IMIP) is to determine a modified weight functionw such that (a)B becomes a maximum weight common independent set of cardinalityk underw, (b)c¦w — w¦ is minimum, and (c)¦w — w b. Many Inverse Combinatorial Optimization Problems can be considered as the special cases of the IMIP.In this paper we show that the IMIP can be solved in strongly polynomial time, and give a necessary and sufficient condition for the feasibility of the IMIP. Finally we extend the discussion to the version of the IMIP with Multiple Common Independent Sets.Research partially supported by the National Natural Science Foundation of China 相似文献
2.
Inverse problem of minimum cuts 总被引:4,自引:0,他引:4
Given a networkN = (V,A,c), a sources V, a. sinkt V and somes —t cuts and suppose each element of the capacity vectorc can be changed with a cost proportional to the changes, the inverse problem of minimum cuts we study here is to change the original capacities with the least total cost under restrictions on the changes of the capacities, so that all thoses —t cuts become minimum cuts with respect to the new capacities.In this paper we shall show that the inverse problem of minimum cuts can be directly transformed into a minimum cost circulation problem and therefore can be solved efficiently by strongly polynomial algorithms.The author is grateful to the partial support of the Universities Grant Council of Hong Kong under the grant CITYU #9040189Work partially supported by the National Natural Science Foundation of China 相似文献
3.
利用收缩技术,证明了1)阶为n=2k且最小半度至少是k的有向图D是强哈密尔顿连通的,除非D属于某些图类;2)2强连通且包含n个顶点、(n-1)(n-2)+4条弧的有向图是强哈密尔顿连通的,除非D属于某些图类. 相似文献
4.
. We introduce the concept of a characterization set for the nucleolus of a cooperative game and develop sufficient conditions
for a collection of coalitions to form a characterization set thereof. Further, we formalize Kopelowitz's method for computing
the nucleolus through the notion of a sequential LP process, and derive a general relationship between the size of a characterization
set and the complexity of computing the nucleolus.
Received May 1994/Revised version May 1997/Final version February 1998 相似文献
5.
Arie Tamir 《Mathematical Programming》1993,59(1-3):117-132
We present strongly polynomial algorithms to find rational and integer flow vectors that minimize a convex separable quadratic cost function on two-terminal series—parallel graphs. 相似文献
6.
7.
提出了求解参数识别反问题的同伦正则化方法,给出了相应的收敛性定理.数值结果表明该方法是一种快速的大范围收敛方法. 相似文献
8.
S. Kindermann 《Numerical Functional Analysis & Optimization》2013,34(2):139-160
In this paper, we consider new regularization methods for linear inverse problems of dynamic type. These methods are based on dynamic programming techniques for linear quadratic optimal control problems. Two different approaches are followed: a continuous and a discrete one. We prove regularization properties and also obtain rates of convergence for the methods derived from both approaches. A numerical example concerning the dynamic EIT problem is used to illustrate the theoretical results. 相似文献
9.
We present the solution of some inverse problems for one-dimensional free boundary problems of oxygen consumption type, with a semilinear convection-diffusion-reaction parabolic equation. Using a fixed domain transformation (Landau's transformation) the direct problem is reduced to a system of ODEs. To minimize the objective functionals in the inverse problems, we approximate the data by a finite number of parameters with respect to which automatic differentiation is applied. 相似文献
10.
A Network Improvement Problem Under Different Norms 总被引:6,自引:0,他引:6
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
, l
1 and l
2 norms to measure the total modification cost respectively. Under l
norm, we present a strongly polynomial 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. 相似文献
11.
关于有向整谱图的若干存在性问题 总被引:1,自引:0,他引:1
系统的回答了[1]在1974年提出的关于有向整谱图的两个问题:1.什么样的非对称强连通有向图是整的?是否存在这样的有向图?2.什么样的多重有向图是整的?。 相似文献
12.
Gap Functions for Equilibrium Problems 总被引:1,自引:0,他引:1
G. Mastroeni 《Journal of Global Optimization》2003,27(4):411-426
The theory of gap functions, developed in the literature for variational inequalities, is extended to a general equilibrium problem. Descent methods, with exact an inexact line-search rules, are proposed. It is shown that these methods are a generalization of the gap function algorithms for variational inequalities and optimization problems. 相似文献
13.
对称的运输问题及其逆问题 总被引:8,自引:0,他引:8
本文对[1,2,6]中提出的运输问题进行了推广,并提出了一个强多项式算法,从而改进了原有的结果.同时对对称的运输问题的逆问题进行了研究,并借助于最小费用循环流技术得到了一个强多项式算法. 相似文献
14.
In optimization, objective functions which are both pseudoconvex and pseudoconcave have been studied extensively. Generalizing these results, we characterize pseudomonotone maps F where -F is also pseudomonotone and explore their properties in variational inequality problems. In particular, we extend recent results by Jeyakumar and Yang which were derived for optimization problems. 相似文献
15.
提出了一类实轴上的双解析函数Riemann边值逆问题.先消去参变未知函数,再采用易于推广的矩阵形式记法,可把问题转化为两个实轴上的解析函数Riemann边值问题.利用经典的Riemann边值问题理论,讨论了该问题正则型情况的解法,得到了它的可解性定理. 相似文献
16.
研究了通过矩阵A的顺序主子矩阵A_((k))=(aij)_(i,j=1)(n-k+1)的特征值{λ_i(n-k+1)的特征值{λ_i((k)))}_(i=1)((k)))}_(i=1)(n-k+1)k=1,2,…,r+1来构造一个带比例关系的实带状矩阵的特征值反问题.对当特征值{λ_i(n-k+1)k=1,2,…,r+1来构造一个带比例关系的实带状矩阵的特征值反问题.对当特征值{λ_i((k))}_(i=1)((k))}_(i=1)(n-k+1)中有多重特征值出现时,应当如何来构造这类矩阵进行了讨论,并给出了问题的具体算法及数值例子. 相似文献
17.
单叶调和映照的反函数 总被引:2,自引:0,他引:2
设是在一个单连通区域上的单叶调和映照,我们证明了反函数z=f-1()也是调和映照的充要条件是f为下面三类函数之一:(i)单叶共形映照;(ii)仿射交换映照;(iii)具有形式f(z)=A[az+β+log(1-e-az-β)-log(1-e-az-β)]+B的调和映照,其中A,B,α和β是常数且满足条件R(az+β)>0,Z∈D. 相似文献
18.
In this paper, we consider questions related to the structure of inverse matrices of linear bounded operators acting in infinite-dimensional complex Banach spaces. We obtain specific estimates of elements of inverse matrices for bounded operators whose matrices have a special structure. Matrices are introduced as special operator-valued functions on an index set. The matrix structure is described by the behavior of the given function on elements of a special partition of the index set. The method used for deriving the estimates is based on an analysis of Fourier series of strongly continuous periodic functions. 相似文献
19.
In this paper, we study restricted NCP functions which may be used to reformulate the nonlinear complementarity problem as a constrained minimization problem. In particular, we consider three classes of restricted NCP functions, two of them introduced by Solodov and the other proposed in this paper. We give conditions under which a minimization problem based on a restricted NCP function enjoys favorable properties, such as equivalence between a stationary point of the minimization problem and the nonlinear complementarity problem, strict complementarity at a solution of the minimization problem, and boundedness of the level sets of the objective function. We examine these properties for three restricted NCP functions and show that the merit function based on the restricted NCP function proposed in this paper enjoys favorable properties compared with those based on the other restricted NCP functions. 相似文献
20.
In order to estimate error bounds on the computed Drazin inverse of a matrix, we need to establish some perturbation theory for the Drazin inverse which is analogous to that for the Moore–Penrose inverse. In this paper, we present recent results on this topic, three problems are put forward in this direction. 相似文献