共查询到20条相似文献,搜索用时 15 毫秒
1.
This paper introduces a new algorithm for solving mixed integer programs. The core of the method is an iterative technique for changing the representation of the original mixed integer optimization problem.
Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202.Mathematics Subject Classification (1991):90C11 相似文献
2.
This paper addresses the question of decomposing an infinite family of rational polyhedra in an integer fashion. It is shown
that there is a finite subset of this family that generates the entire family. Moreover, an integer analogue of Carathéodory's
theorem carries over to this general setting. The integer decomposition of a family of polyhedra has some applications in
integer and mixed integer programming, including a test set approach to mixed integer programming.
Received: May 22, 2000 / Accepted: March 19, 2002 Published online: December 19, 2002
Key words. mixed integer programming – test sets – indecomposable polyhedra – Hilbert bases – rational polyhedral cones
This work was supported partially by the DFG through grant WE1462, by the Kultusministerium of Sachsen Anhalt through the
grants FKZ37KD0099 and FKZ 2945A/0028G and by the EU Donet project ERB FMRX-CT98-0202. The first named author acknowledges
the hospitality of the International Erwin Schr?dinger Institute for Mathematical Physics in Vienna, where a main part of
his contribution to this work has been completed.
Mathematics Subject Classification (1991): 52C17, 11H31 相似文献
3.
In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs,
and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the
independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally
well-dominated graphs.
Received: September 13, 2001 Final version received: May 17, 2002
RID="*"
ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093)
RID="†"
ID="†" Supported by RUTCOR
RID="*"
ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093)
05C75, 05C69
Acknowledgments. The authors thank the referees for valuable suggestions. 相似文献
4.
In this paper, we give the classification of self-dual 𝔽5-codes of lengths 14 and 16. Up to equivalence, there are 53 and 535 such codes, respectively. It is also shown that there
is no self-dual [18, 9, 8] code over 𝔽5.
Received: June 18, 2001 Final version received: April 9, 2002
RID="*"
ID="*" Supported in part by the Academy of Finland under grants 44517 and 100500 相似文献
5.
We show that every 4-representative graph embedding in the double torus contains a noncontractible cycle that separates the
surface into two pieces. As a special case, every triangulation of the double torus in which every noncontractible cycle has
length at least 4 has a noncontractible cycle that separates the surface into two pieces.
Received: May 22, 2001 Final version received: August 22, 2002
RID="*"
ID="*" Supported by NSF Grants Numbers DMS-9622780 and DMS-0070613
RID="†"
ID="†" Supported by NSF Grants Numbers DMS-9622780 and DMS-0070430 相似文献
6.
Sung Y. Song 《Graphs and Combinatorics》2002,18(3):655-665
Fusion relations between the association schemes obtained by direct product and wreath product are established via a study
of their matrix representations. The character table of the scheme obtained by the wreath product is described and some algebraic
properties of the products are derived.
Received: May 7, 1999 Final version received: September 24, 1999
RID="*"
ID="*" 1991 Mathematics Subject Classification. Primary 05E30; Secondary 05B99
RID="*"
ID="*" Supported in part by Com 2MaC-KOSEF, POSTECH, Korea
Acknowledgments. The author is indebted to an anonymous referee who provided the complete proof of Theorem 4.2. 相似文献
7.
Dedicated to the memory of Paul Erdős
Let H be a simple graph having no isolated vertices. An (H,k)-vertex-cover of a simple graph G = (V,E) is a collection of subgraphs of G satisfying
1. , for all i = 1, ..., r,
2. ,
3. , for all , and
4. each is in at most k of the . We consider the existence of such vertex covers when H is a complete graph, , in the context of extremal and random graphs.
Received October 31, 1999
RID="*"
ID="*" Supported in part by NSF grant DMS-9627408.
RID="†"
ID="†" Supported in part by NSF grant CCR-9530974.
RID="‡"
ID="‡" Supported in part by OTKA Grants T 030059 and T 29074, FKFP 0607/1999 and by the Bolyai Foundation.
RID="§"
ID="§" Supported in part by NSF grant DMS-9970622. 相似文献
8.
David Applegate Robert Bixby Vašek Chvátal William Cook 《Mathematical Programming》2003,97(1-2):91-153
Dantzig, Fulkerson, and Johnson (1954) introduced the cutting-plane method as a means of attacking the traveling salesman
problem; this method has been applied to broad classes of problems in combinatorial optimization and integer programming.
In this paper we discuss an implementation of Dantzig et al.'s method that is suitable for TSP instances having 1,000,000
or more cities. Our aim is to use the study of the TSP as a step towards understanding the applicability and limits of the
general cutting-plane method in large-scale applications.
Received: December 6, 2002 / Accepted: April 24, 2003
Published online: May 28, 2003
RID="*"
ID="*" Supported by ONR Grant N00014-03-1-0040 相似文献
9.
The purpose of this note is to present a relation between directed best approximations of a rational vector and the elements
of the minimal Hilbert basis of certain rational pointed cones. Furthermore, we show that for a special class of these cones
the integer Carathéodory property holds true.
Received May 6, 1998
RID="*"
ID="*" Supported by a "Leibniz Preis" of the German Science Foundation (DFG) awarded to M. Gr?tschel.
RID="†"
ID="†" Supported by a "Gerhard-Hess-Forschungsf?rderpreis" of the German Science Foundation (DFG). 相似文献
10.
11.
I. Albarreal M.C. Calzada J.L. Cruz E. Fernández-Cara J. Galo M. Marín 《Numerische Mathematik》2002,93(2):201-221
Summary. This paper is concerned with the analysis of the convergence and the derivation of error estimates for a parallel algorithm
which is used to solve the incompressible Navier-Stokes equations. As usual, the main idea is to split the main differential
operator; this allows to consider independently the two main difficulties, namely nonlinearity and incompressibility. The
results justify the observed accuracy of related numerical results.
Received April 20, 2001 / Revised version received May 21, 2001 / Published online March 8, 2002
RID="*"
ID="*" Partially supported by D.G.E.S. (Spain), Proyecto PB98–1134
RID="**"
ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986
RID="**"
ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986
RID="*"
ID="*" Partially supported by D.G.E.S. (Spain), Proyecto PB98–1134
RID="**"
ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986
RID="**"
ID="**" Partially supported by D.G.E.S. (Spain) Proyecto PB96–0986 相似文献
12.
Sándor Jenei 《Archive for Mathematical Logic》2003,42(5):489-514
We generalize the notions of Girard algebras and MV-algebras by introducing rotation-invariant semigroups. Based on a geometrical
characterization, we present five construction methods which result in rotation-invariant semigroups and in particular, Girard
algebras and MV-algebras. We characterize divisibility of MV-algebras, and point out that integrality of Girard algebras follows
from their other axioms.
Received: 7 January 2002 / Revised version: 4 April 2002 /
Published online: 19 December 2002
RID="*"
ID="*" Supported by the National Scientific Research Fund Hungary (OTKA F/032782).
Mathematics Subject Classification (2000): 20M14, 06F05
Key words or phrases: Residuated lattice – Conjunction for non-classical logics 相似文献
13.
Imre Patyi 《Mathematische Annalen》2003,326(3):417-441
Let X be a complex Banach space with a countable unconditional basis, Ω⊂X pseudoconvex open, G a complex Banach Lie group. We show that a Runge–type approximation hypothesis on X, G (which we also prove for G a solvable Lie group) implies that any holomorphic cocycle on Ω with values in G can be resolved holomorphically if it can be resolved continuously.
Received: 1 March 2002 /
Published online: 28 March 2003
Mathematics Subject Classification (2000): 32L05, 32E30, 46G20
RID="*"
ID="*" Kedves Szímuskának.
RID="*"
ID="*" To my dear Wife. 相似文献
14.
In the assignment game framework, we try to identify those assignment matrices in which no entry can be increased without
changing the core of the game. These games will be called buyer-seller exact games and satisfy the condition that each mixed-pair
coalition attains the corresponding matrix entry in the core of the game. For a given assignment game, a unique buyer-seller
exact assignment game with the same core is proved to exist. In order to identify this matrix and to provide a characterization
of those assignment games which are buyer-seller exact in terms of the assignment matrix, attainable upper and lower core
bounds for the mixed-pair coalitions are found. As a consequence, an open question posed in Quint (1991) regarding a canonical
representation of a “45o-lattice” by means of the core of an assignment game can now be answered.
Received: March 2002/Revised version: January 2003
RID="*"
ID="*" Institutional support from research grants BEC 2002-00642 and SGR2001-0029 is gratefully acknowledged
RID="**"
ID="**" The authors thank the referees for their comments 相似文献
15.
We show that every 6-edge connected graph admits a circulation whose range lies in the interval [1,3).
Received March 29, 2000
RID="*"
ID="*" Supported by NATO-CNR Fellowship; this work was done while the author was visiting the Dept. of Mathematics and Statistics
at Simon Fraser University, Canada.
RID="†"
ID="†" Supported by a National Sciences and Engineering Research Council Research Grant 相似文献
16.
It is proved that, for any ɛ>0 and n>n
0(ɛ), every set of n points in the plane has at most triples that induce isosceles triangles. (Here e denotes the base of the natural logarithm, so the exponent is roughly 2.136.) This easily implies the best currently known
lower bound, , for the smallest number of distinct distances determined by n points in the plane, due to Solymosi–Cs. Tóth and Tardos.
Received: February, 2002 Final version received: September 15, 2002
RID="*"
ID="*" Supported by NSF grant CCR-00-86013, PSC-CUNY Research Award 63382-00-32, and OTKA-T-032452
RID="†"
ID="†" Supported by OTKA-T-030059 and AKP 2000-78-21 相似文献
17.
18.
Dedicated to the memory of Paul Erdős
Suppose we have a finite collection of closed convex sets in the plane, (which without loss of generality we can take to be
polygons). Suppose further that among any four of them, some three have non-empty intersection. We show that 13 points are
sufficient to meet every one of the convex sets.
Received October 27, 1999/Revised April 11, 2000
RID="*"
ID="*" Supported by grant OTKA-T-029074.
RID="†"
ID="†" Supported by NSF grant DMS-99-70071, OTKA-T-020914 and OTKA-F-22234. 相似文献
19.
20.