Covering a symmetric poset by symmetric chains

We prove a min-max result on special partially ordered sets, a conjecture of András Frank. As corollaries we deduce Dilworth's theorem and the well-known min-max formula for the minimum size edge cover of a graph.Research supported by the Netherlands Organization for Scientific Research (NWO)     

On Convergence of the Min-Max Compositions of Fuzzy Matrices

In this paper, we study some of properties of the min-max compositions of fuzzy matrices and give out a dual theorem (to Theorem 3 of [4]) about the convergence of the power sequence of min-max compositions of fuzzy matrices.AMS Subject Classification (2000) 15A45 06A06 04A72     

Brambles and independent packings in chordal graphs

An independent packing of triangles is a set of pairwise disjoint triangles, no two of which are joined by an edge. A triangle bramble is a set of triangles, every pair of which intersect or are joined by an edge. More generally, I consider independent packings and brambles of any specified connected graphs, not just triangles. I give a min-max theorem for the maximum number of graphs in an independent packing of any family of connected graphs in a chordal graph, and a dual min-max theorem for the maximum number of graphs in a bramble in a chordal graph.     

Minimax Methods for Open-Loop Equilibra in $N$-Person Differential Games Part II: Duality and Penalty Theory

The equilibrium strategy for $N$-person differential games can be obtained from a min-max problem subject to differential constraints. The differential constraints are treated here by the duality and penalty methods. We first formulate the duality theory. This involves the introduction of $N+1$ Lagrange multipliers: one for each player and one commonly shared by all players. The primal min-max problem thus results in a dual problem, which is a max-min problem with no differential constraints. We develop the penalty theory by penalizing $N+1$ differential constraints. We give a convergence proof which generalizes a theorem due to B.T. Polyak.     

Node coverings with odd chains

A min-max theorem for node coverings with odd chains in bipartite graphs is derived by simple network flow techniques. A characterization of minimum node covering in terms of a special kind of alternating chains is given, an extension of a result of Norman and Rabin on matchings and node coverings by edges is obtained.     

Variation on a theorem of König

A min-max property of bipartite graphs is stated; it is a variation on the theorem of König ‘maximum matching = minimum covering’; one shows that a certain inequality holds for any graph and the equality for bipartite graphs is derived from a simple network flow model.     

Morse indices of critical manifolds generated by min-max methods with compact lie group actions and applications

We derive some upper and lower bounds for Morse indices of critical manifolds generated by min-max principles for functionals invariant under a general compact Lie group or a finite group action. The results generalize the similar results in the nonequivariant (no group action) case. In doing so, we also generalize the extension theorem of Dugundji type in the nonequivariant case to the equivariant (group action) case. As an application, we obtain a precise growth estimate for the whole sequence of critical values given by the min-max procedure for some superquadratic second-order differential equations. It is well-known that this growth estimate is crucial in showing the existence of multiple solutions of some superquadratic perturbed Hamiltonian systems and equations.     

指数型增广拉格朗日函数在广义半无限规划中的应用

本文利用指数型增广拉格朗日函数将一类广义半无限极大极小问题在一定条件下转化为标准的半无限极大极小问题,使它们具有相同的局部与全局最优解.我们给出了两个转化条件:一个是充分与必要条件,另一个是在实际中易于验证的充分条件.通过这种转化,我们给出了广义半无限极大极小问题的一个新的一阶最优性条件.     

On the Existence of Min-Max Minimal Torus

In this paper, we will study the existence problem of min-max minimal torus. We use classical conformal invariant geometric variational methods. We prove a theorem about the existence of min-max minimal torus in Theorem 5.1. First we prove a strong uniformization result (Proposition 3.1) using the method of Ahlfors and Bers (Ann. Math. 72(2):385–404, 1960). Then we use this proposition to choose good parameterization for our min-max sequences. We prove a compactification result (Lemma 4.1) similar to that of Colding and Minicozzi (Width and finite extinction time of Ricci flow, [math.DG], 2007), and then give bubbling convergence results similar to that of Ding et al. (Invent. math. 165:225–242, 2006). In fact, we get an approximating result similar to the classical deformation lemma (Theorem 1.1).     

Generalized Farkas' theorem and optimization of infinitely constrained problems

This note is concerned with the generalization of Farkas' theorem of the alternative and its application to derive the necessary optimality conditions for min-max problems with satisfaction conditions. Farkas' theorem is generalized to a system of linear inequalities with max operations. The problems studied require a solution at which the worst objective value attains its minimum over a set of solutions fulfilling satisfaction conditions. The satisfaction conditions claim that plural performance criteria should be kept below the permissible level, whatever disturbances may happen or whatever opponents' decisions may be taken. We present a generalized Farkas' theorem in order to derive the necessary optimality conditions for the problems of this class.     

Generalized edge packings

An extension of matchings is considered: instead of edges we use odd length chains all of which have distinct endpoints. We show that several properties of matchings can be extended to these packings: an augmenting chain theorem is given, several variations of packings are described and corresponding min-max results for bipartite graphs are stated. Relations with analogous covering problems are exhibited and we show that these packings generate matroids as in the matching case.     

Partitions into odd chains

An odd chain packingP in a graph is an edge-disjoint collection of odd length chains (and even cycles) such that each node is the endpoint of at most one chain ofP. We define the ocp partition number of a graphG as the smallestk such that the edge setG can be partitioned intok odd chain packings. A min-max theorem is given for bipartite graphs: it is an analogue of the second theorem of König. Some remarks on the corresponding covering problem are given and some other odd chain problems are mentioned.     

熵正则化方法与指数(乘子)罚函数法之间的关系

由于极大极小问题在许多科学与工程中有着重要应用,特别是形如max的函数频繁地出现在各类数值分析和优化问题中,因此对于求解该类问题的算法研究长久不衰,这些算法一般分为两大类：一类是直接法,其算法设计仅以有效地求解原问题（P）为目的;另一类是间接法,其算法以找一个能够替代不可微max函数φ（x）的光滑函数为目的,故这类算法被称为光滑化方法,文[1,2]中的熵正则化方法就属于光滑化方法范畴。     

一类广义半无限规划问题的一阶最优性条件

本文利用一个精确增广Lagrange函数研究了一类广义半无限极小极大规划问题。在一定的条件下将其转化为标准的半无限极小极大规划问题。研究了这两类问题的最优解和最优值之间的关系,利用这种关系和标准半无限极小极大规划问题的一阶最优性条件给出了这类广义半无限极小极大规划问题的一个新的一阶最优性条件。     

Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions

We consider submodular programs which are problems of minimizing submodular functions on distributive lattices with or without constraints. We define a convex (or concave) conjugate function of a submodular (or supermodular) function and show a Fenchel-type min-max theorem for submodular and supermodular functions. We also define a subgradient of a submodular function and derive a necessary and sufficient condition for a feasible solution of a submodular program to be optimal, which is a counterpart of the Karush-Kuhn-Tucker condition for convex programs. This work is supported by the Alexander von Humboldt fellowship (1982/83), West Germany.     

Discrete convex analysis

A theory of “discrete convex analysis” is developed for integer-valued functions defined on integer lattice points. The theory parallels the ordinary convex analysis, covering discrete analogues of the fundamental concepts such as conjugacy, subgradients, the Fenchel min-max duality, separation theorems and the Lagrange duality framework for convex/nonconvex optimization. The technical development is based on matroid-theoretic concepts, in particular, submodular functions and exchange axioms. Sections 1–4 extend the conjugacy relationship between submodularity and exchange ability, deepening our understanding of the relationship between convexity and submodularity investigated in the eighties by A. Frank, S. Fujishige, L. Lovász and others. Sections 5 and 6 establish duality theorems for M- and L-convex functions, namely, the Fenchel min-max duality and separation theorems. These are the generalizations of the discrete separation theorem for submodular functions due to A. Frank and the optimality criteria for the submodular flow problem due to M. Iri-N. Tomizawa, S. Fujishige, and A. Frank. A novel Lagrange duality framework is also developed in integer programming. We follow Rockafellar’s conjugate duality approach to convex/nonconvex programs in nonlinear optimization, while technically relying on the fundamental theorems of matroid-theoretic nature.     

Complexity of the min-max and min-max regret assignment problems

This paper investigates the complexity of the min-max and min-max regret assignment problems both in the discrete scenario and interval data cases. We show that these problems are strongly NP-hard for an unbounded number of scenarios. We also show that the interval data min-max regret assignment problem is strongly NP-hard.     

Bounds for min-max heaps

Very recently a new data structure, called a min-max heap, was presented for implementing the double-ended priority queue. A min-max heap onn keys is constructed inO(n) time; the minimum and maximum keys are found in constant time, and the operations of deleting the minimum, deleting the maximum and inserting a new key into the heap are performed inO(logn) time. In addition, the data structure can be stored implicitly, i.e. in an array ofn elements without using any additional pointers.In this paper, we present lower bound results on the number of comparisons required, in the worst case, for the operations i) to construct a min-max heap on a given set of keys; ii) to convert a min-max heap into a max-min heap; and iii) to merge two min-max heaps into one min-max heap. New upper bounds for the convert and merge operations are also derived. It is found that the main difference between traditional heaps and min-max heaps lies in the time needed to perform the merge operation. While traditional heaps can be merged efficiently, it is shown that min-max heaps are not sublinearly mergeable. Even the seemingly simple task of converting a min-max heap into a max-min heap cannot be performed in less than linear time.This research was supported by the Natural Science and Engineering Council of Canada under Grant No. A0392. (A preliminary version of this paper was presented at the 24th Annual Allerton Conference on Communication, Control and Computing.)