共查询到20条相似文献,搜索用时 0 毫秒
1.
This short note proves that the least square nucleolus (Ruiz et al. (1996)) and the lexicographical solution (Sakawa and Nishizaki (1994)) select the same imputation in each game with nonempty imputation set. As a consequence the least square nucleolus is a general nucleolus (Maschler et al. (1992)). Received: December 1998/Revised version: July 1999 相似文献
2.
On the core of ordered submodular cost games 总被引:5,自引:0,他引:5
A general ordertheoretic linear programming model for the study of matroid-type greedy algorithms is introduced. The primal restrictions are given by so-called weakly increasing submodular functions on antichains. The LP-dual is solved by a Monge-type greedy algorithm. The model offers a direct combinatorial explanation for many integrality results in discrete optimization. In particular, the submodular intersection theorem of Edmonds and Giles is seen to extend to the case with a rooted forest as underlying structure. The core of associated polyhedra is introduced and applications to the existence of the core in cooperative game theory are discussed. Received: November 2, 1995 / Accepted: September 15, 1999?Published online February 23, 2000 相似文献
3.
This paper studies a class of delivery problems associated with the Chinese postman problem and a corresponding class of delivery
games. A delivery problem in this class is determined by a connected graph, a cost function defined on its edges and a special
chosen vertex in that graph which will be referred to as the post office. It is assumed that the edges in the graph are owned
by different individuals and the delivery game is concerned with the allocation of the traveling costs incurred by the server,
who starts at the post office and is expected to traverse all edges in the graph before returning to the post office. A graph
G is called Chinese postman-submodular, or, for short, CP-submodular (CP-totally balanced, CP-balanced, respectively) if for
each delivery problem in which G is the underlying graph the associated delivery game is submodular (totally balanced, balanced, respectively).
For undirected graphs we prove that CP-submodular graphs and CP-totally balanced graphs are weakly cyclic graphs and conversely.
An undirected graph is shown to be CP-balanced if and only if it is a weakly Euler graph. For directed graphs, CP-submodular
graphs can be characterized by directed weakly cyclic graphs. Further, it is proven that any strongly connected directed graph
is CP-balanced. For mixed graphs it is shown that a graph is CP-submodular if and only if it is a mixed weakly cyclic graph.
Finally, we note that undirected, directed and mixed weakly cyclic graphs can be recognized in linear time.
Received May 20, 1997 / Revised version received August 18, 1998?Published online June 11, 1999 相似文献
4.
Levent Tunçel 《Mathematical Programming》1999,86(1):219-223
Given an m×n integer matrix A of full row rank, we consider the problem of computing the maximum of ∥B
-1
A∥2 where B varies over all bases of A. This quantity appears in various places in the mathematical programming literature. More recently, logarithm of this number
was the determining factor in the complexity bound of Vavasis and Ye’s primal-dual interior-point algorithm. We prove that
the problem of approximating this maximum norm, even within an exponential (in the dimension of A) factor, is NP-hard. Our proof is based on a closely related result of L. Khachiyan [1].
Received November 13, 1998 / Revised version received January 20, 1999? Published online May 12, 1999 相似文献
5.
Xiaotie Deng Toshihide Ibaraki Hiroshi Nagamochi Wenan Zang 《Mathematical Programming》2000,87(3):441-452
Combinatorial optimization games deal with cooperative games for which the value of every subset of players is obtained by
solving a combinatorial optimization problem on the resources collectively owned by this subset. A solution of the game is
in the core if no subset of players is able to gain advantage by breaking away from this collective decision of all players.
The game is totally balanced if and only if the core is non-empty for every induced subgame of it.?We study the total balancedness
of several combinatorial optimization games in this paper. For a class of the partition game [5], we have a complete characterization
for the total balancedness. For the packing and covering games [3], we completely clarify the relationship between the related
primal/dual linear programs for the corresponding games to be totally balanced. Our work opens up the question of fully characterizing
the combinatorial structures of totally balanced packing and covering games, for which we present some interesting examples:
the totally balanced matching, vertex cover, and minimum coloring games.
Received: November 5, 1998 / Accepted: September 8, 1999?Published online February 23, 2000 相似文献
6.
In high-multiplicity scheduling problems, identical jobs are encoded in the efficient format of describing one of the jobs
and the number of identical jobs. Similarly, identical machines are efficiently encoded in the same manner. We investigate
parallel-machine, high-multiplicity problems, where there are three possible machine speed structures: identical, proportional,
or unrelated. For the objectives of minimizing the sum of job completion times and minimizing the makespan, we consider both
nonpreemptive and preemptive problems. For some problems, we develop polynomial time algorithms. For several problems, we
demonstrate that the recognition versions can be solved in polynomial time, while the optimization versions require pseudo-polynomial
time. We also show that changing from standard binary encoding to high-multiplicity encoding does not affect the complexity
class of NP-complete problems.
Received: April 1996 / Accepted: July 2000?Published online January 17, 2001 相似文献
7.
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 相似文献
8.
Henk Norde 《Mathematical Programming》1999,85(1):35-49
Received April 21, 1995 / Revised version received June 12, 1998 Published online November 24, 1998 相似文献
9.
On the complexity of a class of combinatorial optimization problems with uncertainty 总被引:2,自引:0,他引:2
Igor Averbakh 《Mathematical Programming》2001,90(2):263-272
We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of m elements with uncertainty in weights of the elements. We present a polynomial algorithm with the order of complexity O((min {p,m-p})2
m) for the case where uncertainty is represented by means of interval estimates for the weights. We show that the problem is
NP-hard in the case of an arbitrary finite set of possible scenarios, even if there are only two possible scenarios. This
is the first known example of a robust combinatorial optimization problem that is NP-hard in the case of scenario-represented
uncertainty but is polynomially solvable in the case of the interval representation of uncertainty.
Received: July 1998 / Accepted: May 2000?Published online March 22, 2001 相似文献
10.
11.
In this paper we consider a two-person zero-sum discounted stochastic game with ARAT structure and formulate the problem of
computing a pair of pure optimal stationary strategies and the corresponding value vector of such a game as a vertical linear
complementarity problem. We show that Cottle-Dantzig’s algorithm (a generalization of Lemke’s algorithm) can solve this problem
under a mild assumption.
Received July 8, 1998 / Revised version received April 16, 1999? Published online September 15, 1999 相似文献
12.
Marion Scheepers 《Archive for Mathematical Logic》1999,38(2):103-122
For X a separable metric space and an infinite ordinal, consider the following three games of length : In ONE chooses in inning an –cover of X; TWO responds with a . TWO wins if is an –cover of X; ONE wins otherwise. In ONE chooses in inning a subset of which has the zero function in its closure, and TWO responds with a function . TWO wins if is in the closure of ; otherwise, ONE wins. In ONE chooses in inning a dense subset of , and TWO responds with a . TWO wins if is dense in ; otherwise, ONE wins. After a brief survey we prove:
1. If is minimal such that TWO has a winning strategy in , then is additively indecomposable (Theorem 4)
2. For countable and minimal such that TWO has a winning strategy in on X, the following statements are equivalent (Theorem 9):
a) TWO has a winning strategy in on .
b) TWO has a winning strategy in on .
3. The Continuum Hypothesis implies that there is an uncountable set X of real numbers such that TWO has a winning strategy in on X (Theorem 10).
Received: 14 February 1997 相似文献
13.
Most of the known efficient algorithms designed to compute the nucleolus for special classes of balanced games are based on two facts: (i) in any balanced game, the coalitions which actually determine the nucleolus are essential; and (ii) all essential coalitions in any of the games in the class belong to a prespecified collection of size polynomial in the number of players. We consider a subclass of essential coalitions, called strongly essential coalitions, and show that in any game, the collection of strongly essential coalitions contains all the coalitions which actually determine the core, and in case the core is not empty, the nucleolus and the kernelcore. As an application, we consider peer group games, and show that they admit at most 2n−1 strongly essential coalitions, whereas the number of essential coalitions could be as much as 2n−1. We propose an algorithm that computes the nucleolus of an n-player peer group game in time directly from the data of the underlying peer group situation.Research supported in part by OTKA grant T030945. The authors thank a referee and the editor for their suggestions on how to improve the presentation 相似文献
14.
This paper is about set packing relaxations of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and set
packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines
carry over to the problems under investigation.
Received: September 1997 / Accepted: November 1999?Published online June 8, 2000 相似文献
15.
$$Osqrt{n}L$$ ); otherwise, the complexity bound is O(nL). The relations between our search direction and the one used in the standard interior-point algorithm are also discussed. Received September 9, 1996 / Revised version received December 22, 1997? Published online March 16, 1999 相似文献
16.
Received August 29, 1996 / Revised version received May 1, 1998 Published online October 21, 1998 相似文献
17.
Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions 总被引:5,自引:0,他引:5
In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family
of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the
polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following
algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the
context of SOCP, that is they have an O( logε-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh,
Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms
for SOCP based on this search direction.
Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000 相似文献
18.
19.
Pierre Chardaire 《Mathematical Programming》2001,90(1):147-151
In the paper “On the nucleolus of the basic vehicle routing game”, Mathematical Programming 72, 83–100 (1996), G?the-Lundgren et al. develop a constraint generation method to compute the pre-nucleolus of a game. Their
method assumes that constraints that are redundant in the representation of the core can be ignored in the computation of
the pre-nucleolus. We provide an example that shows that for a game with an empty core such an assumption is, in general,
not valid. Further, we show that a statement made by G?the-Lundgren et al. about an intuitive interpretation of the pre-nucleolus
is misleading.
Received: January 1996 / Accepted: February 2000?Published online January 17, 2001 相似文献
20.
Summary This paper considers the Γ-component additive games which take into account the possibilities of communications among agents
located in the nodes of a tree graph Γ. Gains from cooperation are derived from agents who are directly connected in the tree.
We introduce a new procedure to compute the nucleolus for these games. This procedure is quick and it does not use linear
programming techniques. We finally present a numerical example of a sequencing game to illustrate the procedure.
This research has been supported partially by UPV-EHU research projects: 035.321-HA 130/93 and GV research proyects: 035.321-0046/93. 相似文献