Equidistribution of Kronecker sequences along closed horocycles

It is well known that (i) for every irrational number the Kronecker sequence m (m = 1,...,M) is equidistributed modulo one in the limit , and (ii) closed horocycles of length become equidistributed in the unit tangent bundle of a hyperbolic surface of finite area, as . In the present paper both equidistribution problems are studied simultaneously: we prove that for any constant the Kronecker sequence embedded in along a long closed horocycle becomes equidistributed in for almost all , provided that . This equidistribution result holds in fact under explicit diophantine conditions on (e.g. for = 2) provided that , with additional assumptions on the Fourier coefficients of certain automorphic forms. Finally, we show that for , our equidistribution theorem implies a recent result of Rudnick and Sarnak on the uniformity of the pair correlation density of the sequence n² modulo one.     

Two algorithms for matroids

A matroid may be characterized by the collection of its bases or by the collection of its circuits. Along with any matroid is a uniquely determined dual matroid. Given the bases of a matroid, it is possible to show that base complements are precisely the bases of the dual. So it is easy to construct bases of the dual given the bases of the original matroid.This paper provides two results. The first enables construction of all circuits of the dual matroid from circuits of the original matroid. The second constructs all bases of a matroid from its circuits.     

Two algorithms for the exchange lemma

Numerical Algorithms - In this note, we present two new algorithms for the Steinitz Exchange Lemma. They are grounded on a single application of a procedure (finding either a row echelon form or a...     

Two algorithms for the Student-Project Allocation problem

We study the Student-Project Allocation problem (SPA), a generalisation of the classical Hospitals/Residents problem (HR). An instance of SPA involves a set of students, projects and lecturers. Each project is offered by a unique lecturer, and both projects and lecturers have capacity constraints. Students have preferences over projects, whilst lecturers have preferences over students. We present two optimal linear-time algorithms for allocating students to projects, subject to the preference and capacity constraints. In particular, each algorithm finds a stable matching of students to projects. Here, the concept of stability generalises the stability definition in the HR context. The stable matching produced by the first algorithm is simultaneously best-possible for all students, whilst the one produced by the second algorithm is simultaneously best-possible for all lecturers. We also prove some structural results concerning the set of stable matchings in a given instance of SPA. The SPA problem model that we consider is very general and has applications to a range of different contexts besides student-project allocation.     

Two algorithms for global optimization

In this paper, we develop and compare two methods for solving the problem of determining the global maximum of a function over a feasible set. The two methods begin with a random sample of points over the feasible set. Both methods then seek to combine these points into “regions of attraction” which represent subsets of the points which will yield the same local maximums when an optimization procedure is applied to points in the subset. The first method for constructing regions of attraction is based on approximating the function by a mixture of normal distributions over the feasible region and the second involves attempts to apply cluster analysis to form regions of attraction. The two methods are then compared on a set of well-known test problems.     

Equidistribution of Hecke eigenforms on the modular surface

For the orthonormal basis of Hecke eigenforms in , one can associate with it a probability measure on the modular surface . We establish that this new measure tends weakly to the invariant measure on as tends to infinity, and obtain a sharp estimate for the rate of convergence.

     

Some properties of horocycles on Damek-Ricci spaces

We prove that a Damek-Ricci space is symmetric if and only if the geodesic inversion preserves the set of horocycles.     

Two exact algorithms for the capacitated p-median problem

The p-median problem has been widely studied in combinatorial optimisation, but its generalisation to the capacitated case has not. We propose a branch and price algorithm, comparing it with a standard MIP solver and a branch and bound algorithm based on Lagrangean relaxation. We present computational experience, using test instances drawn from the literature and new instances with higher ratio between the number of medians p and the number of nodes N. The branch and price algorithm shows very good performances and computational time robustness in solving problems for any ratio.Received: December 2002, Revised: August 2003AMS classification: 90C10, 90C27     

Two phase algorithms for the bi-objective assignment problem

In this paper, we present several algorithms for the bi-objective assignment problem. The algorithms are based on the two phase method, which is a general technique to solve multi-objective combinatorial optimisation (MOCO) problems.     

Two algorithms for weighted matroid intersection

Consider a finite setE, a weight functionw:E→R, and two matroidsM ₁ andM ₂ defined onE. The weighted matroid intersection problem consists of finding a setI⊆E, independent in both matroids, that maximizes Σ{w(e):e inI}. We present an algorithm of complexity O(nr(r+c+logn)) for this problem, wheren=|E|,r=min(rank(M ₁), rank (M ₂)),c=max (c ₁,c ₂) and, fori=1,2,c _i is the complexity of finding the circuit ofI∪{e} inM _i (or show that none exists) wheree is inE andI⊆E is independent inM ₁ andM ₂. A related problem is to find a maximum weight set, independent in both matroids, and of given cardinalityk (if one exists). Our algorithm also solves this problem. In addition, we present a second algorithm that, given a feasible solution of cardinalityk, finds an optimal one of the same cardinality. A sensitivity analysis on the weights is easy to perform using this approach. Our two algorithms are related to existing algorithms. In fact, our framework provides new simple proofs of their validity. Other contributions of this paper are the existence of nonnegative reduced weights (Theorem 6), allowing the improved complexity bound, and the introduction of artificial elements, allowing an improved start and flexibility in the implementation of the algorithms. This research was supported in part by NSF grant ECS 8503192 to Carnegie-Mellon University.     

Two noniterative algorithms for computing posteriors

In this paper, we first propose a noniterative sampling method to obtain an i.i.d. sample approximately from posteriors by combining the inverse Bayes formula, sampling/importance resampling and posterior mode estimates. We then propose a new exact algorithm to compute posteriors by improving the PMDA-Exact using the sampling-wise IBF. If the posterior mode is available from the EM algorithm, then these two algorithms compute posteriors well and eliminate the convergence problem of Markov Chain Monte Carlo methods. We show good performances of our methods by some examples.     

Research on the target coverage algorithms for 3D curved surface

To solve the target covering problems in three-dimensional space, putting forward a deployment strategies of the target points innovatively, and referencing to the differential evolution (DE) algorithm to optimize the location coordinates of the sensor nodes to realize coverage of all the target points in 3-D surface with minimal sensor nodes. Firstly, building the three-dimensional perception model of sensor nodes, and putting forward to the blind area existing in the process of the sensor nodes sensing the target points in 3-D surface innovatively, then proving the feasibility of solving the target coverage problems in 3-D surface with DE algorithm theoretically, and reflecting the fault tolerance of the algorithm.     

Equation describing Hilbert's modular surface

One forwards the idea of obtaining the equation of a modular algebraic surface with the aid of the Hirzebruch curves.Translated from Zapiski Nuachnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 129, pp. 177–181, 1983.The author expresses his gratitude to A. I. Vinogradov for his interest in this paper.     

Two backtrack algorithms for the radio frequency intermodulation problem

Two or more radio signals, transmitted from a small platform (e.g., a ship, satellite, or airplane, etc.), tend to produce an intermodulation product which could distort a receive signal. The intensity of intermodulation interference due to a given intermodulation frequency is known to be closely related to the lowest order, or simply the order, of the intermodulation product which can be found by solving a single constraint integer program with variables unrestricted in sign, where coefficients of the constraint equation correspond to frequencies. Two variations of backtrack, or search enumeration, algorithms, called the primal and dual backtrack algorithms, are developed to find the order of intermodulation. Extensive computational experience with these algorithms, reflecting data from naval fleet communication scenarios and potential ramifications, are given together with another application of the dual algorithm.This work was supported by the Office of Naval Research (ONR) under Contract No. N00014-78C-0028. We are grateful to the Naval Ocean Systems Center (NOSC) and, in particular, to Dr. John Rockway, Walter Chase, and Dr. S. T. Li for their cooperation. Appreciation is also extended to Dr. Neal Glassman at ONR, Washington, D.C., and Dr. Dennis G. McCall at NOSC, for introducing us to the problem area.     

Two algorithms for a plant-storehouse location problem

Summary This paper considers the following assignment problem. There are some groups of plants, each group producing a different commodity. There are some consumption areas, each containing a number of storehouses and wanting a certain amount of all the commodities. The problem consists of finding the assignment of storehouses to plants which minimizes the overall cost, consisting of fixed charges associated to all storehouses and plants, and of transportation costs. For the solution of this problem, which can be called a plant-storehouse location problem, two algorithms are presented. The first algorithm makes use of a branch and bound technique; the second is based on a decomposition technique, which follows directly from the Dynamic Programming.The classic plant location problem is a particular case of the problem discussed in this paper.

---

Zusammenfassung In dieser Arbeit wird folgendes Zuordnungsproblem untersucht. Gegeben sind einige Fabrikgruppen, die jeweils verschiedene Waren herstellen, und einige Verbrauchsgebiete mit jeweils einer Anzahl von Lägern und einem bestimmten Bedarf an diesen Waren. Gesucht ist eine gesamtkostenminimale Zuordnung der Läger zu den Fabriken. Die Gesamtkosten setzen sich aus den Transportkosten und fixed charges für jede Fabrik und jedes Lager zusammen. Für dieses spezielle Standortproblem werden zwei Algorithmen entwickelt. Während der erste Algorithmus auf der Branch and Bound-Technik aufbaut, basiert der zweite auf einer aus der dynamischen Optimierung entwickelten Dekompositionstechnik.Das klassische Standorproblem ist ein Sonderfall des in dieser Arbeit behandelten Problems.

---

---

Deutsche Übersetzung:Zwei Algorithmen zur Lösung von Fabrik-Lagerhaus-Standortproblemen.

---

This work has been supported by Consiglio Nazionale delle Ricerche (C. N. R.), Roma, Italy.

---

The authors are with the Istituto di Elettrotecnica ed Elettronica, Laboratorio di Controlli Automatici, Politecnico di Milano, Milano, Italy.