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.)     

A las vegas rnc algorithm for maximum matching

Recently two randomized algorithms were discovered that find a maximum matching in an arbitrary graph in polylog time, when run on a parallel random access machine. Both are Monte Carlo algorithms — they have the drawback that with non-zero probability the output is a non-maximum matching. We use the min-max formula for the size of a maximum matching to convert any Monte Carlo maximum matching algorithm into a Las Vegas (error-free) one. The resulting algorithm returns (with high probability) a maximum matching and a certificate proving that the matching is indeed maximum. Research supported by DARPA grant N00039-84-C-0098 and by a US Army Research Office fellowship.     

Approximating a two-machine flow shop scheduling under discrete scenario uncertainty

This paper deals with the two machine permutation flow shop problem with uncertain data, whose deterministic counterpart is known to be polynomially solvable. In this paper, it is assumed that job processing times are uncertain and they are specified as a discrete scenario set. For this uncertainty representation, the min-max and min-max regret criteria are adopted. The min-max regret version of the problem is known to be weakly NP-hard even for two processing time scenarios. In this paper, it is shown that the min-max and min-max regret versions of the problem are strongly NP-hard even for two scenarios. Furthermore, the min-max version admits a polynomial time approximation scheme if the number of scenarios is constant and it is approximable with performance ratio of 2 and not (4/3 − ?)-approximable for any ? > 0 unless P = NP if the number of scenarios is a part of the input. On the other hand, the min-max regret version is not at all approximable even for two scenarios.     

Shifting algorithms for tree partitioning with general weighting functions

Recently two shifting algorithms were designed for two optimum tree partitioning problems: The problem of max-min q-partition [4] and the problem of min-max q-partition [1]. In this work we investigate the applicability of these two algorithms to max-min and min-max partitioning of a tree for various different weighting functions. We define the families of basic and invariant weighting functions. It is shown that the first shifting algorithm yields a max-min q-partition for every basic weighting function. The second shifting algorithm yields a min-max q-partition for every invariant weighting function. In addition a modification of the second algorithm yields a min-max q-partition for the noninvariant diameter weighting function.     

Constrained ratio games and generalized fractional programming

A certain constrained ratio game is shown to be equivalent to a pair of mutually dual generalized fractional programming problems. This also extends the concept of symmetric duality to min-max fractional programming.Research by this author was carried out while he was visiting I.I.T. Delhi, India, under an Australian Vice-Chancellors' Committee Visiting Fellowship.     

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

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

Existence of constant mean curvature 2-Spheres in Riemannian 3-spheres

We prove the existence of branched immersed constant mean curvature (CMC) 2-spheres in an arbitrary Riemannian 3-sphere for almost every prescribed mean curvature, and moreover for all prescribed mean curvatures when the 3-sphere is positively curved. To achieve this, we develop a min-max scheme for a weighted Dirichlet energy functional. There are three main ingredients in our approach: a bi-harmonic approximation procedure to obtain compactness of the new functional, a derivative estimate of the min-max values to gain energy upper bounds for min-max sequences for almost every choice of mean curvature, and a Morse index estimate to obtain another uniform energy bound required to reach the remaining constant mean curvatures in the presence of positive curvature.     

Packing Non-Returning <Emphasis Type="Italic">A</Emphasis>-Paths*

Chudnovsky et al. gave a min-max formula for the maximum number of node-disjoint nonzero A-paths in group-labeled graphs [1], which is a generalization of Mader's theorem on node-disjoint A-paths [3]. Here we present a further generalization with a shorter proof. The main feature of Theorem 2.1 is that parity is “hidden” inside , which is given by an oracle for non-bipartite matching. * Research is supported by OTKA grants T 037547 and TS 049788, by European MCRTN Adonet, Contract Grant No. 504438 and by the Egerváry Research Group of the Hungarian Academy of Sciences. † The author is a member of the Egerváry Research Group (EGRES).     

On realizing symmetric 3-polytopes

We prove the analogue of Eberhard’s Theorem for symmetric convex 3-polytopes with a 4-valent graph, and disprove a conjecture of the late T. Motzkin about realizing symmetric convex 3-polytopes so that all of their geodesics are in planes. This research was supported by the National Research Council of Canada Grant A-3999.     

A Berry-Esseen bound for symmetric statistics

Summary The rate of convergence of the distribution function of a symmetric function of N independent and identically distributed random variables to its normal limit is investigated. Under appropriate moment conditions the rate is shown to be (N^–1/2). This theorem generalizes many known results for special cases and two examples are given. Possible further extensions are indicated.Research supported by the U.S. Office of Naval Research, Contract N 00014-80-C-0163     

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

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

THE MORSE CRITICAL GROUPS OF THE MINMAX THEOREM

The author gives a new min-max theorem and studies the local homology propertiesof critical points that is got by min-max theorem.In particular,this result includes manymin-max theorem of link type,which can be applicable to nonlinear analysis.     

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.     

Approximation hardness of min-max tree covers

We prove the first inapproximability bounds to study approximation hardness for a min-max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees. Our technique can also be applied to improve inapproximability bounds for min-max problems that use other covering objectives, such as stars, paths, and tours.     

RUC-decompositions in symmetric operator spaces

We show that ifX is a Banach space of type 2 andG is a compact Abelian group, then any system of eigenvectors {x }_G (with respect to a strongly continuous representation ofG onX) is an RUC-system. As an application, we exhibit new examples of RUC-bases in certain symmetric spaces of measurable operators.Research supported by the Australian Research Council     

Weakly symmetric spaces and spherical varieties

Weakly symmetric homogeneous spaces were introduced by A. Selberg in 1956. We prove that, for a real reductive algebraic group, they can be characterized as the spaces of real points of affine spherical homogeneous varieties of the complexified group. As an application, under the same assumption on the transitive group, we show that weakly symmetric spaces are precisely the homogeneous Riemannian manifolds with commutative algebra of invariant differential operators.Supported by the Alexander von Humboldt Foundation and Russian Foundation for Basic Research, Grant No. 95-01-01263.Supported by the U. S. Civilian Research and Development Foundation, Award No. 206, Russian Foundation for Basic Research, Grant No. 98-01-00598, and the Alexander von Humboldt Foundation.     

The kadec-klee property in symmetric spaces of measurable operators

We show that ifE is a separable symmetric Banach function space on the positive half-line thenE has the Kadec-Klee property if and only if, for every semifinite von Neumann algebra (M, τ), the associated spaceE(M, τ) ofτ-measurable operators has the Kadec-Klee property. Research supported by the Australian Research Council.     

The parity problem of polymatroids without double circuits

According to the present state of the theory of the matroid parity problem, the existence of a good characterization to the size of a maximum matching depends on the behavior of certain substructures, called double circuits. In this paper we prove that if a polymatroid has no double circuits then a partition type min-max formula characterizes the size of a maximum matching. Applications to parity constrained orientations and to a rigidity problem are given. Research is supported by OTKA grants K60802, TS049788 and by European MCRTN Adonet, Contract Grant No. 504438.     

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).     

Fully symmetric operator spaces

It is shown that certain interpolation theorems for non-commutative symmetric operator spaces can be deduced from their commutative versions. A principal tool is a refinement of the notion of Schmidt decomposition of a measurable operator affiliated with a given semi-finite von Neumann algebra.Research supported by A.R.C.