Explicit min–max polynomials on the disc

Denote by ${\Pi }_{n+m?1}^2?\{{\sum }_{0\le i+j\le n+m?1}{c}_{i,j}{x}^i{y}^j:c_{i,j}\in \mathbb{R}\}$ the space of polynomials of two variables with real coefficients of total degree less than or equal to $n+m?1$. Let $b_0,b_1,\dots ,b_l\in \mathbb{R}$ be given. For $n,m\in \mathbb{N},n\ge l+1$ we look for the polynomial $b_0{x}^n{y}^m+b_1{x}^{n?1}{y}^{m+1}+?+b_l{x}^{n?l}{y}^{m+l}+q(x,y),q(x,y)\in {\Pi }_{n+m?1}^2$, which has least maximum norm on the disc and call such a polynomial a min–max polynomial. First we introduce the polynomial $2P_{n,m}(x,y)=x{G}_{n?1,m}(x,y)+y{G}_{n,m?1}(x,y)=2x^n{y}^m+q(x,y)$ and $q(x,y)\in {\Pi }_{n+m?1}^2$, where $G_{n,m}(x,y)?1/2^{n+m}(U_n\left(x\right)U_m\left(y\right)+U_{n?2}\left(x\right)U_{m?2}\left(y\right))$, and show that it is a min–max polynomial on the disc. Then we give a sufficient condition on the coefficients $b_j,j=0,\dots ,l,l$ fixed, such that for every $n,m\in \mathbb{N},n\ge l+1$, the linear combination ${\sum }_{\nu =0}^l{b}_{\nu }{P}_{n?\nu ,m+\nu }(x,y)$ is a min–max polynomial. In fact the more general case, when the coefficients $b_j$ and $l$ are allowed to depend on $n$ and $m$, is considered. So far, up to very special cases, min–max polynomials are known only for $x^n{y}^m$,$n,m\in {\mathbb{N}}_0$.     

Semidefinite programming for min–max problems and games

We consider two min–max problems (1) minimizing the supremum of finitely many rational functions over a compact basic semi-algebraic set and (2) solving a 2-player zero-sum polynomial game in randomized strategies with compact basic semi-algebraic sets of pure strategies. In both problems the optimal value can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre (SIAM J Optim 11:796–817, 2001; Math Program B 112:65–92, 2008). This provides a unified approach and a class of algorithms to compute Nash equilibria and min–max strategies of several static and dynamic games. Each semidefinite relaxation can be solved in time which is polynomial in its input size and practice on a sample of experiments reveals that few relaxations are needed for a good approximation (and sometimes even for finite convergence), a behavior similar to what was observed in polynomial optimization.     

Modeling max–min fair bandwidth allocation in BitTorrent communities

This paper gives an exact mathematical programming model and algorithm of the max–min fairness bandwidth allocation problem in multi-swarm peer-to-peer content sharing community. The proposed iterative method involves solution of LP and MILP problems of large scale. Based on real-world data traces, numerical experiments demonstrate that the new algorithm is computationally faster than an earlier developed one for larger problem sizes, and it provides better numerical stability. Moreover, even if its execution is stopped after some initial steps it still grants feasible solution with good approximation to max–min fairness.     

Thresholded covering algorithms for robust and max–min optimization

In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the \(k\) -robust model where the possible scenarios tomorrow are given by all demand-subsets of size \(k\) . In this paper, we give the following simple and intuitive template for \(k\) -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for \(k\) -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our \(k\) -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal–dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max–min problems of the form: “given a covering problem instance, which \(k\) of the elements are costliest to cover?” For the problems mentioned above, we show that their \(k\) -max–min versions have performance guarantees similar to those for the \(k\) -robust problems.     

A weighted max–min model for fuzzy goal programming

After Narasimhan's pioneering study of applying fuzzy set theory to goal programming in 1980, many achievements in the field have been recorded. Most of them followed the max–min approach. However, when objectives have different levels of importance, only the weighted additive model of Tiwari et al. seems to be applicable. However, the shortcoming of the additive model is that the summation of quasiconcave functions may not be quasiconcave. This study proposes a novel weighted max–min model for fuzzy goal programming (FGP) and for fuzzy multiple objective decision-making. The proposed model adapts well to even the most complicated membership functions. Numerical examples demonstrate that the proposed model can be effectively incorporated with other approaches to FGP and is superior to the weighted additive approach.     

Min–max and min–max (relative) regret approaches to representatives selection problem

The following optimization problem is studied. There are several sets of integer positive numbers whose values are uncertain. The problem is to select one representative of each set such that the sum of the selected numbers is minimum. The uncertainty is modeled by discrete and interval scenarios, and the min?Cmax and min?Cmax (relative) regret approaches are used for making a selection decision. The arising min?Cmax, min?Cmax regret and min?Cmax relative regret optimization problems are shown to be polynomially solvable for interval scenarios. For discrete scenarios, they are proved to be NP-hard in the strong sense if the number of scenarios is part of the input. If it is part of the problem type, then they are NP-hard in the ordinary sense, pseudo-polynomially solvable by a dynamic programming algorithm and possess an FPTAS. This study is motivated by the problem of selecting tools of minimum total cost in the design of a production line.     

Min–max and min–max regret versions of combinatorial optimization problems: A survey

Min–max and min–max regret criteria are commonly used to define robust solutions. After motivating the use of these criteria, we present general results. Then, we survey complexity results for the min–max and min–max regret versions of some combinatorial optimization problems: shortest path, spanning tree, assignment, min cut, min s–t cut, knapsack. Since most of these problems are NP-hard, we also investigate the approximability of these problems. Furthermore, we present algorithms to solve these problems to optimality.     

A generalized min–max theorem for functionals of strongly indefinite sign

We consider non-linear Schrödinger equations of the following type: $$\begin{aligned} \left\{ \begin{array}{l} -\Delta u(x) + V(x)u(x)-q(x)|u(x)|^\sigma u(x) = \lambda u(x), \quad x\in \mathbb{R }^N \\ u\in H^1(\mathbb{R }^N)\setminus \{0\}, \end{array} \right. \end{aligned}$$ where $N\ge 1$ and $\sigma >0$ . We will concentrate on the case where both $V$ and $q$ are periodic, and we will analyse what happens for different values of $\lambda $ inside a spectral gap $]\lambda ^-,\lambda ^+[$ . We derive both the existence of multiple orbits of solutions and the bifurcation of solutions when $\lambda \nearrow \lambda ^+$ . Thereby we use the corresponding energy function ${I_\lambda }$ and we derive a new variational characterization of multiple critical levels for such functionals: in this way we get multiple orbits of solutions. One main advantage of our new view on some specific critical values $c_0(\lambda )\le c_1(\lambda )\le \cdots \le c_n(\lambda )\le \cdots $ is a multiplicity result telling us something about the number of critical points with energies below $c_n(\lambda )$ , even if for example two of these values $c_i(\lambda )$ and $c_j(\lambda )$ ( $0\le i<j\le n$ ) coincide. Let us close this summary by mentioning another main advantage of our variational characterization of critical levels: we present our result in an abstract setting that is suitable for other problems and we give some hints about such problems (like the case corresponding to a Coulomb potential $V$ ) at the end of the present paper.     

Max–min Bin Packing Algorithm and its application in nano-particles filling

With regard to existing bin packing algorithms, higher packing efficiency often leads to lower packing speed while higher packing speed leads to lower packing efficiency. Packing speed and packing efficiency of existing bin packing algorithms including NFD, NF, FF, FFD, BF and BFD correlates negatively with each other, thus resulting in the failure of existing bin packing algorithms to satisfy the demand of nano-particles filling for both high speed and high efficiency. The paper provides a new bin packing algorithm, Max–min Bin Packing Algorithm (MM), which realizes both high packing speed and high packing efficiency. MM has the same packing speed as NFD (whose packing speed ranks no. 1 among existing bin packing algorithms); in case that the size repetition rate of objects to be packed is over 5, MM can realize almost the same packing efficiency as BFD (whose packing efficiency ranks No. 1 among existing bin packing algorithms), and in case that the size repetition rate of objects to be packed is over 500, MM can achieve exactly the same packing efficiency as BFD. With respect to application of nano-particles filling, the size repetition rate of nano particles to be packed is usually in thousands or ten thousands, far higher than 5 or 500. Consequently, in application of nano-particles filling, the packing efficiency of MM is exactly equal to that of BFD. Thus the irreconcilable conflict between packing speed and packing efficiency is successfully removed by MM, which leads to MM having better packing effect than any existing bin packing algorithm. In practice, there are few cases when the size repetition of objects to be packed is lower than 5. Therefore the MM is not necessarily limited to nano-particles filling, and can also be widely used in other applications besides nano-particles filling. Especially, MM has significant value in application of nano-particles filling such as nano printing and nano tooth filling.     

Constrained inverse min–max spanning tree problems under the weighted Hamming distance

In this paper, we consider the constrained inverse min–max spanning tree problems under the weighted Hamming distance. Three models are studied: the problem under the bottleneck-type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in strongly polynomial times. This research is supported by the National Natural Science Foundation of China (Grant No. 10601051).     

A min–max vehicle routing problem with split delivery and heterogeneous demand

In this article, we introduce a new variant of min–max vehicle routing problem, where various types of customer demands are satisfied by heterogeneous fleet of vehicles and split delivery of services is allowed. We assume that vehicles may serve one or more types of service with unlimited service capacity, and varying service and transfer speed. A heuristic solution approach is proposed. We report the solutions for several test problems.     

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.     

A metaheuristic for the min–max windy rural postman problem with K vehicles

In this paper we deal with the min–max version of the windy rural postman problem with K vehicles. For this problem, in which the objective is to minimize the length of the longest tour in order to find a set of balanced tours for the vehicles, we present here a metaheuristic that produces very good feasible solutions in reasonable computing times. It is based on the combination of a multi-start procedure with an Iterated Local Search. Extensive computational results on a large set of instances with up to 50 vertices, 184 edges and 5 vehicles are presented. The results are very good, the average gaps with respect to a known lower bound are less than 0.40% for instances with 2 or 3 vehicles and up to 1.60% when 4 or 5 vehicles are considered.     

A novel piecewise linear classifier based on polyhedral conic and max–min separabilities

In this paper, an algorithm for finding piecewise linear boundaries between pattern classes is developed. This algorithm consists of two main stages. In the first stage, a polyhedral conic set is used to identify data points which lie inside their classes, and in the second stage we exclude those points to compute a piecewise linear boundary using the remaining data points. Piecewise linear boundaries are computed incrementally starting with one hyperplane. Such an approach allows one to significantly reduce the computational effort in many large data sets. Results of numerical experiments are reported. These results demonstrate that the new algorithm consistently produces a good test set accuracy on most data sets comparing with a number of other mainstream classifiers.