Minimax and Applications

Frontmatter

Minimax Theorems and Their Proofs

Abstract

We suppose that X and Y are nonempty sets and f: X x Y →IR A minimax theorem is a theorem which asserts that, under certain conditions,

$$\mathop{{\min }}\limits_{Y} \mathop{{\max }}\limits_{X} f = \mathop{{\max }}\limits_{X} \mathop{{\min }}\limits_{Y} f.$$

Stephen Simons

A Survey on Minimax Trees And Associated Algorithms

Abstract

This paper surveys theoretical results about minimax game trees and the algorithms used to explore them. The notion of game tree is formally introduced and its relation with game playing described. The first part of the survey outlines major theoretical results about minimax game trees, their size and the structure of their subtrees. In the second part of this paper, we survey the various sequential algorithms that have been developed to explore minimax trees. The last part of this paper tries to give a succinct view on the state of the art in parallel minimax game tree searching.

Claude G. Diderich, Marc Gengler

An Iterative Method for the Minimax Problem

Abstract

In this paper an iterative method for the minimax problem is proposed. The idea is that we present a sequence of the extended linear-quadratic programming (ELQP) problems as subproblems of the original minimax problem and solve the ELQP problems iteratively. Since the ELQP problem can be solved directly or by using methods for linear variational inequality or linear complementarity problem, an iterative method for the minimax problem is obtained. The locally linear and superlinear convergence of the algorithm is established.

Liqun Qi, Wenyu Sun

A Dual and Interior Point Approach to Solve Convex Min-Max Problems

Abstract

In this paper we propose an interior point method for solving the dual form of min-max type problems. The dual variables are updated by means of a scaling supergradient method. The boundary of the dual feasible region is avoided by the use of a logarithmic barrier function. A major difference with other interior point methods is the nonsmoothness of the objective function.

Jos F. Sturm, Shuzhong Zhang

Determining the Performance Ratio of Algorithm Multifit for Scheduling

Abstract

Scheduling n independent tasks nonpreemptively on m identical processors with the aim of minimizing the makespan is well-known to be NP-complete. Coffman, Garey and Johnson [1] described an algorithm-MULTIFIT and proved that it satisfies a bound of 1.22. Friesen [2] showed an example in which the upper bound is no less than 13/11. Yue, Keller and Yu proved an upper bound of 1.2. Yue gave a proof for the upper bound of 13/11, but the proof missed some casesIn this paper, a complete and simple proof is presented.

Feng Cao

A Study of On-Line Scheduling Two-Stage Shops

Abstract

We investigate the problem of on-line scheduling two-stage shops with the objective of minimizing the maximum completion time. We show that for two-stage open shops, no on-line algorithm can have a worst-case performance ratio less than \(\tfrac{1}{2}(1 + \sqrt {5} ) \approx 1.618\) if preemption is not allowed. We provide an on-line heuristic algorithm with worst-case performance ratio 1.875. If preemption is allowed, however, we give an on-line algorithm with worst-case performance ratio 4/3, and show that it is a best possible on-line algorithm. On the other hand, for a two-stage flow shop or job shop, we prove that no on-line algorithm can outperform a simple one, which has a worst-case performance ratio of 2.

Bo Chen, Gerhard J. Woeginger

Maxmin Formulation of the Apportionments of Seats to a Parliament

Abstract

We consider the problem of apportioning a fixed number of seats in a national parliament to the candidates of different parties that are elected in constituencies so as to meet party and constituency constraints. We propose a maxmin formulation of the problem. The purpose is to obtain a fair apportionment of the parliament seats, in the sense that the minimum number of voters behind any possible parliament majority is maximum. We illustrate the concepts with some examples, including an example from the last Icelandic election.

Thorkell Helgason, Kurt Jörnsten, Athanasios Migdalas

On Shortest K-Edge Connected Steiner Networks with Rectilinear Distance

Abstract

In this paper we consider the problem of constructing a shortest k-edge connected Steiner network in the plane with rectilinear distance for k ≥ 2. Given a set of P of points, let l _k(P) denote the length of a shortest k-edge connected Steiner network on P divided by the length of a shortest k-edge connected spanning network on P. We prove that \(\tfrac{3}{4} \leqslant \inf \{ {{l}_{2}}(P)|P\} \tfrac{6}{7}, \tfrac{2}{3} \leqslant \inf \{ {{l}_{3}}(P)|P\} \leqslant \tfrac{7}{8}\). We also show that if all points in P are on the sides of the rectilinear convex hull of P, then l _k(P) = 1, for k is even, and \({{l}_{k}}(P) > \tfrac{{3k + 1}}{{3k + 3}}\), for k is odd.

D. Frank Hsu, Xiao-Dong Hu, Yoji Kajitani

Mutually Repellant Sampling

Abstract

This paper studies the following class of sampling problem: Let (D, || ||) be a metric space whose distance function || || satisfies the triangular equality. Let k be an integer. We would like to find a sample subset of k elements of D that are mutually far away from each other. We study three versions of the “farness” condition and give optimal or close to optimal polynomial-time approximation algorithms for constructing such good samples. Because all three definitions measure different aspects of how one sample element “repel” its close neighbors to be chosen in the sample, we call these sampling problems “mutually repellant sampling”. In applications, the metric space naturally models graphs or geometric domains. The definitions of farness are closed related with the condition that the k-sample best measures the “shape” of a graph or a geometric domain. Our results have applications in several graph partitioning algorithms and optimization heuristics. Furthermore, our algorithms are on-line in the sense that they do not have to know k in advance.

Shang-Hua Teng

Geometry and Local Optimality Conditions for Bilevel Programs with Quadratic Strictly Convex Lower Levels

Abstract

This paper describes necessary and sufficient optimality conditions for bilevel programming problems with quadratic strictly convex lower levels. By examining the local geometry of these problems we establish that the set of feasible directions at a given point is composed of a finite union of convex cones. Based on this result, we show that the optimality conditions are simple generalizations of the first and second order optimality conditions for mathematical (one level) programming problems.

Luis N. Vicente, Paul H. Calamai

The Spherical One-Center Problem

Abstract

In this paper we study the spherical one-center problem, i. e., finding a point on a sphere such that the maximum of the geodesic distances from this point to n given points on the sphere is at minimum. We show that this problem can be solved in O(n) time using the multidimensional search technique developed by Megiddo[9] and Dyer[5] when the n given points gill lie within a spherical circle of radius smaller than \(\tfrac{\pi }{2}\) times the radius of the given sphere. We also show that the spherical one-center problem may have multiple solutions when the above condition is not satisfied.

Guoliang Xue, Shangzhi Sun

On Min-Max Optimization of a Collection of Classical Discrete Optimization Problems

Abstract

In this paper, we study discrete optimization problems with min-max objective functions. This type of optimization has long been the attention of researchers, and it has direct applications in the recent development of robust optimization. The following well-known classes of problems are discussed: 1) the minimum spanning tree problem, 2) the resource allocation problem with separable cost functions, and 3) the production control problem. Computational complexities of the corresponding min-max version of the above-mentioned problems are analyzed. Pseudo-polynomial algorithms for these problems under certain conditions are provided.

Gang Yu, Panagiotis Kouvelis

Heilbronn Problem for Six Points in a Planar Convex Body

Abstract

For any six points in a planar convex body K there must be at least one triangle, formed by three of these points, with area not greater than 1/6 of the area of K. This upper bound 1/6 is best possible.

Andreas W. M. Dress, Lu Yang, Zhenbing Zeng

Heilbronn Problem for Seven Points in a Planar Convex Body

Abstract

Let K be a planar convex body (that means a compact convex set with non-empty interior), \K\ the area of K\ for any triangle ri7*27*3, by (rir2r3) denote its area; and let

$$\begin{array}{*{20}{c}} {({{r}_{1}}{{r}_{2}} \cdots {{r}_{n}}) : = \min \{ ({{r}_{i}}{{r}_{j}}{{r}_{k}})|1 \leqslant i < j < k \leqslant n\} ;} \hfill \\ {{{H}_{n}}(K) : = \frac{1}{{|K|}}\sup \{ ({{r}_{1}}{{r}_{2}} \cdots {{r}_{n}})|{{r}_{i}} \in K,i = 1, \cdots ,n\} .} \hfill \\ \end{array}$$

Lu Yang, Zhenbing Zeng

On the Complexity of Min-Max Optimization Problems and their Approximation

Abstract

The computational complexity of optimization problems of the min-max form is naturally characterized by ∏ ₂ ^P , the second level of the polynomial-time hierarchy. We present a number of optimization problems of this form and show that they are complete for the class ∏ ₂ ^P . We also show that the constant–factor approximation versions of some of these optimization problems are also complete for ∏ ₂ ^P .

Ker-I Ko, Chih-Long Lin

A Competitive Algorithm for the Counterfeit Coin Problem

Abstract

The classical counterfeit coin problem asks for the minimum number of weighings on a balance scale to find the counterfeit coin among a set of n coins. The classical problem has been extended to more than one counterfeit coin, but the knowledge of the number of counterfeit coins was previously always assumed. In this paper we assume no such knowledge 0and propose an algorithm with uniform good performance.

X. D. Hu, F. K. Hwang

A Minimax αβ Relaxation for Global Optimization

Abstract

Local minima make search and optimization harder. In this paper, we give a new global optimization approach, minimax aαβ relaxation, to cope with the pathological behavior of local minima. The minimax a αβ relaxation interplays a dual step minimax local to global optimization, an iterative local to global information propagation, and an adaptive local to global algorithm transition, within a parallel processing framework. In minimax αβ relaxation, a controls the rate of local to global information propagation and β controls the rate of algorithm transition from local to global optimization. Compared to the existing optimization approaches such as simulated annealing and local search, the minimax β relaxation demonstrates much better convergence performance for certain classes of constrained optimization problems.¹

Jun Gu

Minimax Problems in Combinatorial Optimization

Abstract

Classical minimax theory initiated by Von Neumann, together with duality and saddle point analysis, has played a critical role in optimization and game theory. However, minimax problems and techniques appear in a very wide area of disciplines. There are many interesting and sophisticated problems formulated as minimax problems. For example, many combinatorial optimization problems, including scheduling, location, allocation, packing, searching, and triangulation, can be represented as a minimax problem. Many of these problems have nothing to do with duality and saddle points, and they have not been considered in any general uniform treatment. Furthermore, many minimax problems have deep mathematical background, nice generalizations, and lead to new areas of research in combinatorial optimization. In this survey, we discuss a small but diverse collection of minimax problems, and we present some results (with a few key references) and open questions.

Feng Cao, Ding-Zhu Du, Biao Gao, Peng-Jun Wan, Panos M. Pardalos

Backmatter