On the bottleneck assignment problem

In this paper, a new approach for solving the bottleneck assignment problem is presented. The problem is treated as a special class of permutation problems which we call max-min permutation problems. By defining a suitable neighborhood system in the space of permutations and designating certain permutations as critical solutions, it is shown that any critical solution yields a global optimum. This theorem is then used as a basis to develop a general method to solve max-min permutation problems.This work was carried out by the junior author while holding a Purdue University Fellowship.     

Duality for nonconvex absolute value programming and a characterization of linear max-min programs

In this paper a dual problem for nonconvex linear programs with absolute value functionals is constructed by means of a max-min problem involving bivalent variables. A relationship between the classical linear max-min problem and a linear program with absolute value functionals is developed. This program is then used to compute the duality gap between some max-min and min-max linear problems.     

Max-min controllability in pursuit games with norm-bounded controls

In this article, we consider max-min controllability in linear pursuit games with norm-bounded controls. Our approach is based on the separation theorem of disjoint compact convex sets in Euclidean space. Necessary and sufficient conditions for max-min controllability are given in terms of an explicit relative controllability expression which, in a sense, is a comparison between the control capabilities of the competing parties. Minimal time and optimal norm problems are investigated.     

A queueing analysis of max-min fairness, proportional fairness and balanced fairness

We compare the performance of three usual allocations, namely max-min fairness, proportional fairness and balanced fairness, in a communication network whose resources are shared by a random number of data flows. The model consists of a network of processor-sharing queues. The vector of service rates, which is constrained by some compact, convex capacity set representing the network resources, is a function of the number of customers in each queue. This function determines the way network resources are allocated. We show that this model is representative of a rich class of wired and wireless networks. We give in this general framework the stability condition of max-min fairness, proportional fairness and balanced fairness and compare their performance on a number of toy networks.     

Stationarity Conditions and Their Reformulations for Mathematical Programs with Vertical Complementarity Constraints

We consider the mathematical program with vertical complementarity constraints. We show that the min-max-min problems and the problems with max-min constraints can be reformulated as the above problem. As a complement of the work of Scheel and Scholtes in 2000, we derive the Mordukhovich-type stationarity conditions for the considered problem. We further reformulate various popular stationarity systems as nonlinear equations with simple constraints. A modified Levenberg–Marquardt method is employed to solve these constrained equations.     

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.     

Modified geometric programming problem and its applications

In this paper, we propose unconstrained and constrained posynomial Geometric Programming (GP) problem with negative or positive integral degree of difficulty. Conventional GP approach has been modified to solve some special typer of GP problems. In specific case, when the degree of difficulty is negative, the normality and the orthogonality conditions of the dual program give a system of linear equations. No general solution vector exists for this system of linear equations. But an approximate solution can be determined by the least square and also max-min method. Here, modified form of geometric programming method has been demonstrated and for that purpose necessary theorems have been derived. Finally, these are illustrated by numerical examples and applications.     

Using the parametric approach to solve the continuous-time linear fractional max–min problems

A numerical algorithm based on parametric approach is proposed in this paper to solve a class of continuous-time linear fractional max-min programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as a parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this algorithm.     

Minimization of maximum absolute deviation in integers

A resource allocation problem of the integer minimization of maximum absolute deviation of monotone functions is under investigation. The optimal solution is shown to belong to one of the four possible classes. The optimality conditions of two kinds (“local” and “global” ones) are derived along with an algorithm, which utilizes the solutions of simple min-max and max-min integer allocation problems.The Apportionment problem is considered as an application.     

无线通信系统设计中的两个优化问题和相关优化方法

无线通信系统设计中的许多问题可建模为优化问题.一方面,这些优化问题常常具有高度的非线性性,一般情况下难于求解;另一方面,它们又有自身的特殊结构,例如隐含的凸性、可分性等.利用优化的方法结合问题的特殊结构求解和处理无线通信系统设计问题是近年来学术界研究的热点.本文重点讨论无线通信系统设计中的两个优化问题和相关优化方法,包括多用户干扰信道最大最小准则下的联合传输/接收波束成形设计和多输入多输出(Multi-Input Multi-Output,MIMO)检测问题,主要介绍现代优化技术结合问题的特殊结构在求解和处理上述两个问题的最新进展.     

拟圆的最大-最小不等式性质

利用区域的最大-最小不等式性质的拟共形不变性和圆的最大-最小不等式性质,得到了拟圆的最大-最小不等式性质.     

Max-min matching problems with multiple assignments

In job assignment and matching problems, we may sometimes need to assign several jobs to one processor or several processors to one job with some limit on the number of permissible assignments. Some examples include the assignment of courses to faculty, consultants to projects, etc. In terms of objectives, we may wish to maximize profits or minimize costs, or maximize the minimal value (max-min criterion) of an attribute such as the performance rating of a processor in the matching, or combine the two goals into one composite objective function entailing time-cost tradeoffs. The regular bipartite matching algorithms cannot solve the matching problem, when upper and lower bounds are imposed on the number of assignments. In this paper, we present a method, referred to as the node-splitting method, that transforms the given problem into an assignment problem solvable by the Hungarian method.     

Certain bivariate distributions and random processes connected with maxima and minima

The minimum and the maximum of t independent, identically distributed random variables have \(\bar F^{t}\) and F ^t for their survival (minimum) and the distribution (maximum) functions, where \(\bar F = 1-F\) and F are their common survival and distribution functions, respectively. We provide stochastic interpretation for these survival and distribution functions for the case when t >?0 is no longer an integer. A new bivariate model with these margins involve maxima and minima with a random number of terms. Our construction leads to a bivariate max-min process with t as its time argument. The second coordinate of the process resembles the well-known extremal process and shares with it the one-dimensional distribution given by F ^t . However, it is shown that the two processes are different. Some fundamental properties of the max-min process are presented, including a distributional Markovian characterization of its jumps and their locations.     

模糊正则文法的逼近性

为了扩大现有研究的应用范围,基于max-min型模糊正则文法引入了max-*型模糊正则文法(其中*为特定t-模)的概念,讨论了max-*型模糊正则文法可以通过max-min型模糊正则文法在任意给定的逼近精度来逼近.研究表明,当t-模*满足一定的条件时,max-*型模糊正则文法与max-min型模糊正则文法在生成模糊语言能力方面是等价的.     

WAVELET TECHNIQUE RECOVERING IMAGE BLURRED BY MIXED GAUSSIAN AND SALT-PEPPER NOISE

In this paper, we propose a new method to removing the mixed Gaussian and salt-popper noise based on wavelet. To estimate outlier, A scheme called max-min method is adopted after DWT. Experimental results show that this method is more effective than common image restoration methods, such as Median filter,comter weighted median filter.     

An interval version of separation by semispaces in max-min convexity

In this paper, we study separation of a closed box from a max-min convex set by max-min semispaces. This can be regarded as an interval extension of the known separation results. We give a constructive proof of the separation in the case when the box satisfies a certain condition, and we show that the separation is never possible when the condition is not satisfied. We also study the separation of two max-min convex sets by a box and by a box and a semispace.     

Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems

Min-max problems on matroids are NP-hard for a wide variety of matroids. However, greedy type algorithms have data independent worst case performance guarantees, andn-enumerative algorithms yield-optimal solutions ifn is sufficiently close to the rank of the underlying matroid. Data dependent performance guarantees can be obtained for max-min problems over matroids.This research was partially supported by NSERC Grant A5543.     

On max-min linear inequalities and Coalitional Resource Games with sharable resources

In a Coalitional Resource Game (CRG for brief), agents form coalitions to pool their resources in order to achieve certain goals, requiring the expenditure of these resources. A particular coalition is said to be successful, if the common resources of its members enable to achieve a set of goals that satisfies all members of the coalition. It is known that when resources are consumable it is NP-complete to decide whether a given coalition is successful. In this paper, we show a connection of CRGs with sharable resources and max-min linear systems of inequalities. This correspondence leads to polynomial algorithms for checking whether a given CRG admits a successful coalition and for several other problems whose counterparts for CRGs with consumable resources are hard. On the other hand, we prove that some problems concerning the structure of successful coalitions are hard also in the case of sharable resources.     

一类新的华氏宏观经济数学模型

提出了一类新的有消费的华氏宏观经济数学模型，给出了相应此模型的一套数学理论（包括主产系统失去和不失去平衡的条件、最大最小原则和正特征矢量法）及有关经济解释。这些内容推广和发展了华罗庚教授生前所做的有关工作。     

不等式组与变分不等式的极大熵函数方法

利用极大熵函数方法将不等式组及变分不等式的求解问题转化为近似可微优化问题，给出了不等式组及变分不等式问题近似解的可微优化方法，得到了不等式组和变分不等式问题的解集合的示性函数．