Symmetry properties of resolving sets and metric bases in hypercubes

In this paper we consider some special characteristics of distances between vertices in the \(n\)-dimensional hypercube graph \(Q_n\) and, as a consequence, the corresponding symmetry properties of its resolving sets. It is illustrated how these properties can be implemented within a simple greedy heuristic in order to find efficiently an upper bound of the so called metric dimension \(\beta (Q_n)\) of \(Q_n\), i.e. the minimal cardinality of a resolving set in \(Q_n\). This heuristic was applied to generate upper bounds of \(\beta (Q_n)\) for \(n\) up to \(22\), which are for \(n\ge 19\) better than the existing ones. Starting from these new bounds, some existing upper bounds for \(23\le n\le 90\) are improved by a dynamic programming procedure.     

Additive energy and the Hausdorff dimension of the exceptional set in metric pair correlation problems

For a sequence of integers {a(x)} _x≥1 we show that the distribution of the pair correlations of the fractional parts of {〈αa(x)〉} _x≥1 is asymptotically Poissonian for almost all α if the additive energy of truncations of the sequence has a power savings improvement over the trivial estimate. Furthermore, we give an estimate for the Hausdorff dimension of the exceptional set as a function of the density of the sequence and the power savings in the energy estimate. A consequence of these results is that the Hausdorff dimension of the set of α such that {〈αx ^d 〉} fails to have Poissonian pair correlation is at most \(\frac{{d + 2}}{{d + 3}} < 1\). This strengthens a result of Rudnick and Sarnak which states that the exceptional set has zero Lebesgue measure. On the other hand, classical examples imply that the exceptional set has Hausdorff dimension at least \(\frac{2}{{d + 1}}\).An appendix by Jean Bourgain was added after the first version of this paper was written. In this appendix two problems raised in the paper are solved.     

An indirect genetic algorithm for set covering problems

This paper presents a new type of genetic algorithm for the set covering problem. It differs from previous evolutionary approaches first because it is an indirect algorithm, ie the actual solutions are found by an external decoder function. The genetic algorithm itself provides this decoder with permutations of the solution variables and other parameters. Second, it will be shown that results can be further improved by adding another indirect optimisation layer. The decoder will not directly seek out low cost solutions but instead aims for good exploitable solutions. These are then post-optimised by another hill-climbing algorithm. Although seemingly more complicated, we will show that this three-stage approach has advantages in terms of solution quality, speed and adaptability to new types of problems over more direct approaches. Extensive computational results are presented and compared to the latest evolutionary and other heuristic approaches to the same data instances.     

An algorithm to solve polyhedral convex set optimization problems

An algorithm which computes a solution of a set optimization problem is provided. The graph of the objective map is assumed to be given by finitely many linear inequalities. A solution is understood to be a set of points in the domain satisfying two conditions: the attainment of the infimum and minimality with respect to a set relation. In the first phase of the algorithm, a linear vector optimization problem, called the vectorial relaxation, is solved. The resulting pre-solution yields the attainment of the infimum but, in general, not minimality. In the second phase of the algorithm, minimality is established by solving certain linear programs in combination with vertex enumeration of some values of the objective map.     

Geodesics for the capacity metric in doubly connected domains

We give the qualitative behavior of geodesics of the capacity metric defined on the annulus and study the variation of its Gaussian curvature. We make explicit the relation between the capacities, the Bergman kernel and the reduced Bergman kernel on doubly connected domains and give some applications.     

An algorithm for computing minimal curves

Let ?³ be the 3-dimensional projective space over an algebraically closed field K of characteristic 0, and R be the graded polynomial ring K[x ₀,x ₁,x ₂,x ₃]. If C is a curve of ?³, let M _c := ⊕ H ^l I _C (n) be its Hartshorne-Rao module: it is a graded R-module of finite length which, up to a shift in degrees, characterizes the biliaison class of C. M. Martin-Deschamps &; D. Perrin (Sur la classification des courbes gauches. Astérisque 184–185 (1990)) have proved that in every biliaison class of non arithmetically Cohen-Macaulay curves there exists a minimal curve, unique up to a deformation with constant cohomology and Hartshorne-Rao module, that is a curve C such that, if C ₁ is any curve in the biliaison class of C, then M _{C 1} = M _c(?n), with n ≧ 0. They have moreover given an algorithm for the computation of a minimal curve, based on the computation and the analysis of the minors of given orders of some submatrices of the second syzygy matrix σ ₂ of M. The aim of this paper is to give an improvement to the algorithm for computing a minimal curve of a given Hartshorne-Rao module. The key remark is that the information obtained from σ ₂ can analogously be obtained from the matrix f(σ ₂) with entries in the polynomial ring K[u], where f:R → K[u] is a map which evaluates the variables of R to random linear polynomials in K[u]. The advantage of this approach is first, that the computations are done in a simpler polynomial ring and second, that in K[u]|we can take advantage of the Smith Normal Form algorithm to analyze the structure of the minors of the given matrices. The algorithm is therefore probabilistic but rather efficient and allows to compute (the invariants of) a minimal curve associated to modules whose syzygies matrices are considerably large. The algorithms presented here have been partially implemented and tested in the computer algebra systems CoCoA, Maple and Macaulay.     

An algorithm for minimal dynamic flow

FORD and FULKERSON have shown that a stationary maximal dynamic flow can be obtained by solving a transhipment problem associated with the static network and thereby finding the maximal temporally repeated dynamic flow. This flow is known to be an optimal dynamic flow. This paper presents the remark that temporally repeated flows may be not optimal for a minimal dynamic flow and an algorithm for such a flow. A numerical example is presented.     

On the dimension of affine resolvable designs and hypercubes

The equivalence between complete sets of mutually orthogonal hypercubes and affine resolvable designs, which generalizes the well-known equivalence between complete sets of mutually orthogonal latin squares and affine planes, is used to examine the dimension of designs by studying the prime classes in the associated hypercubes. Particular attention is given to designs of order n=9 including a design which is nonisomorphic to AG(3, 9) even though it possesses the same parameters and three prime classes. © 1996 John Wiley & Sons, Inc.     

An algorithm for reconstructing controls in a uniform metric

The problem of the dynamic reconstruction of unknown controls acting on a non-linear vector differential equation is discussed. Two regularizing algorithms are presented that enable these controls to be reconstructed in a uniform metric synchronously with the development of the processes considered. The algorithms are stable to information noise and errors in the calculations.     

An algorithm for set covering problem

In this paper we present an algorithm for the set covering problem that combines problem reduction tests with dual ascent, subgradient optimisation and linear programming. Computational results are presented for problems involving up to 400 rows and 4000 columns.     

Note: An algorithm to solve polyhedral convex set optimization problems

We provide a counterexample to the remark in Löhne and Schrage [An algorithm to solve polyhedral convex set optimization problems, Optimization 62 (2013), pp. 131-141] that every solution of a polyhedral convex set optimization problem is a pre-solution. A correct statement is that every solution of a polyhedral convex set optimization problem obtained by the algorithm SetOpt is a pre-solution. We also show that every finite infimizer and hence every solution of a polyhedral convex set optimization problem contains a pre-solution.     

An interior point algorithm to solve computationally difficult set covering problems

We present an interior point approach to the zero–one integer programming feasibility problem based on the minimization of a nonconvex potential function. Given a polytope defined by a set of linear inequalities, this procedure generates a sequence of strict interior points of this polytope, such that each consecutive point reduces the value of the potential function. An integer solution (not necessarily feasible) is generated at each iteration by a rounding scheme. The direction used to determine the new iterate is computed by solving a nonconvex quadratic program on an ellipsoid. We illustrate the approach by considering a class of difficult set covering problems that arise from computing the 1-width of the incidence matrix of Steiner triple systems.     

An algorithm for optimizing over the weakly-efficient set

In this paper a bisecting search algorithm is developed for solving the problem (P) of optimizing a linear function over the set of weakly-efficient solutions of a multiple objective linear program. We show that problem (P) can arise in a variety of practical situations. The algorithm for solving problem (P) is guaranteed to find an optimal or approximately-optimal solution for the problem in a finite number of steps. Using a Fortran computer code called Conmin as an aid, we have solved ten test problems using our proposed algorithm. This preliminary computational experience seems to indicate that the algorithm is quite practical for relatively small problems.     

An algorithm for the difference between set covers

A set cover for a set S is a collection C of special subsets whose union is S. Given covers A and B for two sets, the set-cover difference problem is to construct a new cover for the elements covered by A but not B. Applications include testing equivalence of set covers and maintaining a set cover dynamically. In this paper, we solve the set-cover difference problem by defining a difference operation A-B, which turns out to be a pseudocomplement on a distributive lattice. We give an algorithm for constructing this difference, and show how to implement the algorithm for two examples with applications in computer science: face covers on a hypercube, and rectangle covers on a grid. We derive an upper bound on the time complexity of the algorithm, and give upper and lower bounds on complexity for face covers and rectangle covers.     

An optimal algorithm for finding minimal enclosing triangles

Klee and Laskowski's O(n log²n) algorithm for finding all minimal area triangles enclosing a given convex polygon of n vertices is improved to Θ(n), which is shown to be optimal both for finding all minima and for finding just one.     

平方度量动态设施选址问题的近似算法

研究了单阶段度量设施选址问题的推广问题平方度量动态设施选址问题. 研究中首先利用原始对偶技巧得到 9-近似算法, 然后利用贪婪增广技巧将近似比改进到2.606, 最后讨论了该问题的相应变形问题.