Minimum-Area ellipse containing a finite set of points. I

From the geometric point of view, we consider the problem of construction of a minimum-area ellipse containing a given convex polygon. For an arbitrary triangle, we obtain an equation for the boundary of the minimum-area ellipse in explicit form. For a quadrangle, the problem of construction of a minimumarea ellipse is connected with the solution of a cubic equation. For an arbitrary polygon, we prove that if the boundary of the minimum-area ellipse has exactly three common points with the polygon, then this ellipse is the minimum-area ellipse for the triangle obtained. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 7, pp. 980–988, July, 1998.     

Orderings based on the banks set: Some new scoring methods for multicriteria decision making

This article introduces new methods for ranking alternatives in multicriteria decision making situations. Each is based on the normative position that the strength of an alternative is inversely related to the number of alternatives that could prevent it from being chosen. The scores discriminate among elements of the Banks set (Banks, Soc Choice Welfare, 1985, 1, 295–306). The new scoring methods are compared to traditional scoring methods and related to the amount of intransitivity (specifically, the size of the top‐cycle) of aggregated preference. The new scores are shown to measure important aspects of alternatives not captured by extant scoring methods and are illustrated in collective choice settings. © 2014 Wiley Periodicals, Inc. Complexity 20: 63–76, 2015     

Some exact iterative procedures for finding the puncture point of a convex set

LetK be a convex set in the Hilbert spaceH, and let the ray {c: R} punctureK at *c. Some algorithms are given for finding *. Each algorithm results in a nonincreasing sequence { _i } which converges to *. The points _j c lie in successive supporting hyperplanes toK. The normal to thenth hyperplane is obtained by a minimization over a set no larger than the unitn cube. It is assumed that the subset ofK which maximizes (,x) forx inK is found relatively easily.This research was sponsored by NSF Grant No. MCS-76-11040.     

Solvable Groups Satisfying the Two-prime Hypothesis,Part I

In this paper, finite solvable groups satisfying the “-prime hypothesis” are considered. Specifically, a bound on the number of irreducible character degrees of such a group is obtained when . The general situation is also considered, and generalizations of the -prime hypothesis are analyzed. Presented by A. Verschoren.     

The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case

The Two-Dimensional Finite Bin Packing Problem (2BP) consists of determining the minimum number of large identical rectangles, bins, that are required for allocating without overlapping a given set of rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. In this paper we describe new lower bounds for the 2BP where the items have a fixed orientation and we show that the new lower bounds dominate two lower bounds proposed in the literature. These lower bounds are extended in Part II (see Boschetti and Mingozzi 2002) for a more general version of the 2BP where some items can be rotated by . Moreover, in Part II a new heuristic algorithm for solving both versions of the 2BP is presented and computational results on test problems from the literature are given in order to evaluate the effectiveness of the proposed lower bounds.     

Bergman interpolation on finite Riemann surfaces. Part I: asymptotically flat case

The article considers the Bergman space interpolation problem on open Riemann surfaces obtained from a compact Riemann surface by removing a finite number of points. Such a surface is equipped with what we call an asymptotically flat conformal metric, i.e., a complete metric with zero curvature outside a compact subset. Sufficient conditions for interpolation in weighted Bergman spaces over asymptotically flat Riemann surfaces are then established. When the weights have curvature that is quasi-isometric to the asymptotically flat boundary metric, these sufficient conditions are shown to be necessary, unless the surface has at least one cylindrical end, in which case, the necessary conditions are slightly weaker than the sufficient conditions.     

Incomplete decision contexts: Approximate concept construction,rule acquisition and knowledge reduction

Incomplete decision contexts are a kind of decision formal contexts in which information about the relationship between some objects and attributes is not available or is lost. Knowledge discovery in incomplete decision contexts is of interest because such databases are frequently encountered in the real world. This paper mainly focuses on the issues of approximate concept construction, rule acquisition and knowledge reduction in incomplete decision contexts. We propose a novel method for building the approximate concept lattice of an incomplete context. Then, we present the notion of an approximate decision rule and an approach for extracting non-redundant approximate decision rules from an incomplete decision context. Furthermore, in order to make the rule acquisition easier and the extracted approximate decision rules more compact, a knowledge reduction framework with a reduction procedure for incomplete decision contexts is formulated by constructing a discernibility matrix and its associated Boolean function. Finally, some numerical experiments are conducted to assess the efficiency of the proposed method.     

Evolutionary,constructive and hybrid procedures for the bi-objective set packing problem

The bi-objective set packing problem is a multi-objective combinatorial optimization problem similar to the well-known set covering/partitioning problems. To our knowledge and surprise, this problem has not yet been studied whereas several applications have been reported. Unfortunately, solving the problem exactly in a reasonable time using a generic solver is only possible for small instances. We designed three alternative procedures for approximating solutions to this problem. The first is derived from the original ‘Strength Pareto Evolutionary Algorithm’, which is a population-based metaheuristic. The second is an adaptation of the ‘Greedy Randomized Adaptative Search Procedure’, which is a constructive metaheuristic. As underlined in the overview of the literature summarized here, almost all the recent, effective procedures designed for approximating optimal solutions to multi-objective combinatorial optimization problems are based on a blend of techniques, called hybrid metaheuristics. Thus, the third alternative, which is the primary subject of this paper, is an original hybridization of the previous two metaheuristics. The algorithmic aspects, which differ from the original definition of these metaheuristics, are described, so that our results can be reproduced. The performance of our procedures is reported and the computational results for 120 numerical instances are discussed.     

On the Character Degree Graph of Solvable Groups, I Three Primes

For any finite solvable group G we show that if three primes dividing the degrees of certain irreducible characters of G are given, then there exists an irreducible character of G with degree divisible by at least two of the given primes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Facets and lifting procedures for the set covering polytope

Given a family of subsets of an arbitrary groundsetE, acover of is any setC E having non-empty intersection with every subset in. In this paper we deal with thecovering polytope, i.e., the convex hull of the incidence vectors of all the covers of. In Section 2 we review all the known properties of the covering polytope. In Sections 3 and 4 we introduce two new classes of non-Boolean facets of such a polytope. In Sections 5 and 6 we describe some non-sequential lifting procedures. In Section 7 a generalization of the notion ofweb introduced by L.E. Trotter is presented together with the facets of the covering polytope produced by such a structure.Moreover, the strong connections between several combinatorial problems and the covering problem are pointed out and, exploiting those connections, some examples are presented of new facets for the Knapsack and Acyclic Subdigraph polytopes.     

Reduced Weyl asymptotics for pseudodifferential operators on bounded domains I. The finite group case

Let G⊂O(n) be a compact group of isometries acting on n-dimensional Euclidean space Rn, and X a bounded domain in Rn which is transformed into itself under the action of G. Consider a symmetric, classical pseudodifferential operator A₀ in L²(Rn) with G-invariant Weyl symbol, and assume that it is semi-bounded from below. We show that the spectrum of the Friedrichs extension A of the operator is discrete, and derive asymptotics for the number Nχ(λ) of eigenvalues of A less or equal λ and with eigenfunctions in the χ-isotypic component of L²(X) as λ→∞, giving also an estimate for the remainder term in case that G is a finite group. In particular, we show that the multiplicity of each unitary irreducible representation in L²(X) is asymptotically proportional to its dimension.     

Designing local orthogonal bases on finite groups I: Abelian case

We extend to general finite groups a well-known relation used for checking the orthogonality of a system of vectors as well as for orthogonalizing a nonorthogonal one. This, in turn, is used for designing local orthogonal bases obtained by unitary transformations of a single prototype filter. The first part of this work considers abelian groups. The second part considers nonabelian groups where, as an example, we show how to build such bases where the group of unitary transformations consists of modulations and rotations. These bases are useful for building systems for evaluating image quality.     

A finite,nonadjacent extreme-point search algorithm for optimization over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple-objective linear program serves many useful purposes in multiple-criteria decision making. Mathematically, problem (P) can be classified as a global optimization problem. Such problems are much more difficult to solve than convex programming problems. In this paper, a nonadjacent extreme-point search algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact extreme-point optimal solution for the problem after a finite number of iterations. It can be implemented using only linear programming methods. Convergence of the algorithm is proven, and a discussion is included of its main advantages and disadvantages.The author owes thanks to two anonymous referees for their helpful comments.