Codes with given distances

One of the main results says that ifC is a binary linear code of length 4t and of dimension greater than 2t, thenC contains a word of weight 2t and this bound is best possible. Several results of similar flavor are established both for linear and non-linear codes. For the proof a lemma introducing the binormal forms of binary matrices is needed. The results are applied to determine the coset chromatic number of Hadamard graphs, to solve a problem of Galvin and to give a short proof of a theorem of Gleason on self-dual doubly-even codes.     

Art networks with geometrical distances

In this paper, ART networks (Fuzzy ART and Fuzzy ARTMAP) with geometrical norms are presented. The category choice of these networks is based on the L_p norm. Geometrical properties of these architectures are presented. Comparisons between this category choice and the category choice of the ART networks are illustrated. And simulation results on the databases taken from the UCI repository are performed. It will be shown that using the L_p norm is geometrically more attractive. It will operate directly on the input patterns without the need for doing any preprocessing. It should be noted that the ART architecture requires two preprocessing steps: normalization and complement coding. Simulation results on different databases show the good generalization performance of the Fuzzy ARTMAP with L_p norm compared to the performance of a typical Fuzzy ARTMAP.     

Point sets with distinct distances

For positive integersd andn letf _d (n) denote the maximum cardinality of a subset of then ^d -gird {1,2,...,n} ^d with distinct mutual euclidean distances. Improving earlier results of Erds and Guy, it will be shown thatf ₂ (n)c·n ^2/3 and, ford3, thatf _d (n)c _d ·n ^2/3 ·(lnn)^1/3, wherec, c _d >0 are constants. Also improvements of lower bounds of Erds and Alon on the size of Sidon-sets in {1²,22²,...,n ²} are given.Furthermore, it will be proven that any set ofn points in the plane contains a subset with distinct mutual distances of sizec ₁·n ^1/4, and for point sets in genral position, i.e. no three points on a line, of sizec ₂·n ^1/3 with constantsc ₁,c ₂>0. To do so, it will be shown that forn points in ² with distinct distancesd ₁,d ₂,...,d _t , whered _i has multiplicitym _i , one has _i=1 ^t m _i ² c·n _3.25 for a positive constantc. If then points are in general position, then we prove _i=1 ^t m _i ² c·n ₃ for a positive constantc and this bound is tight.Moreover, we give an efficient sequential algorithm for finding a subset of a given set with the desired properties, for example with distinct distances, of size as guaranteed by the probabilistic method under a more general setting.     

Bounds on sets with few distances

We derive a new estimate of the size of finite sets of points in metric spaces with few distances. The following applications are considered:

•

we improve the Ray-Chaudhuri-Wilson bound of the size of uniform intersecting families of subsets;

•

we refine the bound of Delsarte-Goethals-Seidel on the maximum size of spherical sets with few distances;

•

we prove a new bound on codes with few distances in the Hamming space, improving an earlier result of Delsarte.

We also find the size of maximal binary codes and maximal constant-weight codes of small length with 2 and 3 distances.     

Convex nonagons with five intervertex distances

The vertices of a convex planar nonagon determine exactly five distances if and only if they are nine vertices of a regular 10-gon or a regular 11-gon. This result has important ties to related concerns, including the maximum number of points in the plane that determine exactly five distances and, for each n7, the samllest t for which there exists a convex n-gon whose vertices determine t distances and are not all on one circle.     

Rao distances

We determine Riemannian distances between a large class of multivariate probability densities with the same mean, where the Riemannian metric is induced by a weighted Fisher information matrix. We reduce the evaluation of distances to quadrature and in some cases give closed form expressions.     

Minisum location problem with farthest Euclidean distances

The paper formulates an extended model of Weber problem in which the customers are represented by convex demand regions. The objective is to generate a site in R ² that minimizes the sum of weighted Euclidean distances between the new facility and the farthest points of demand regions. This location problem is decomposed into a polynomial number of subproblems: constrained Weber problems (CWPs). A projection contraction method is suggested to solve these CWPs. An algorithm and the complexity analysis are presented. Three techniques of bound test, greedy choice and choice of starting point are adopted to reduce the computational time. The restricted case of the facility is also considered. Preliminary computational results are reported, which shows that with the above three techniques adopted the algorithm is efficient.The authors were supported by the dissertation fund of Nari-Relays Corporation.     

Triangles with given distances from a centre

A number of generalized functions rigorously used in the mathematical theories of science are developed in the form of double‐point functions to follow the principle of causality. Various features are also discussed as a critical note.     

Scheduling with few changes

In this work we consider scheduling problems where a sequence of assignments from products to machines – or from tasks to operators, or from workers to resources – has to be determined, with the goal of minimizing the costs (=money, manpower, and/or time) that are incurred by the interplay between those assignments. To account for the different practical requirements (e.g. few changes between different products/tasks on the same machine/operator, few production disruptions, or few changes of the same worker between different resources), we employ different objective functions that are all based on elementary combinatorial properties of the schedule matrix. We propose simple and efficient algorithms to solve the corresponding optimization problems, and provide hardness results where such algorithms most likely do not exist.     

Set covering location models with stochastic critical distances

This paper formulates a new version of set covering models by introducing a customer-determined stochastic critical distance. In this model, all services are provided at the sites of facilities, and customers have to go to the facility sites to obtain the services. Due to the randomness of their critical distance, customers patronize a far or near facility with a probability. The objective is to find a minimum cost set of facilities so that every customer is covered by at least one facility with an average probability greater than a given level α. We consider an instance of the problem by embedding the exponential effect of distance into the model. An algorithm based on two searching paths is proposed for solutions to the instance. Experiments show that the algorithm performs well for problems with greater α, and the experimental results for smaller α are reported and analysed.     

Weber problems with mixed distances and regional demand

We consider a location problem where the distribution of the existing facilities is described by a probability distribution and the transportation cost is given by a combination of transportation cost in a network and continuous distance. The motivation is that in many cases transportation cost is partly given by the cost of travel in a transportation network whereas the access to the network and the travel from the exit of the network to the new facility is given by a continuous distance.      

Online Scheduling with Hard Deadlines

We study non-preemptive, online admission control in the hard deadline model: each job must either be serviced prior to its deadline or be rejected. Our setting consists of a single resource that services an online sequence of jobs; each job has a length indicating the length of time for which it needs the resource and a delay indicating the maximum time it can wait for the service to be started. The goal is to maximize total resource utilization. The jobs are non-preemptive and exclusive, meaning once a job begins, it runs to completion, and at most one job can use the resource at any time. We obtain a series of results, under varying assumptions of job lengths and delays.     

带调整时间的一类排序问题

进一步讨论带磨损因子的排序问题,在相应问题中对工件j,j=1,2,…,n,引入了调整时间sj,它同磨损因子bj一样同该工件何时加工无关.要求适当排列这n个工件的加工顺序,使目标函数值达最小.给出了加工全程、完工时间之和及JIT问题在引入调整时间下的最优算法.     

Scheduling with step-improving processing times

We consider the scheduling problem of minimizing the makespan on a single machine with step-improving job processing times around a common critical date. For this problem we give an NP-hardness proof, a fast pseudo-polynomial time algorithm, an FPTAS, and an on-line algorithm with best possible competitive ratio.     

Scheduling with unexpected machine breakdowns

We investigate an online version of a basic scheduling problem where a set of jobs has to be scheduled on a number of identical machines so as to minimize the makespan. The job processing times are known in advance and preemption of jobs is allowed. Machines are non-continuously available, i.e., they can break down and recover at arbitrary time instances not known in advance. New machines may be added as well. Thus machine availabilities change online. We first show that no online algorithm can construct optimal schedules. We also show that no online algorithm can achieve a bounded competitive ratio if there may be time intervals where no machine is available. Then we present an online algorithm that constructs schedules with an optimal makespan of C_max^OPT if a lookahead of one is given, i.e., the algorithm always knows the next point in time when the set of available machines changes. Finally, we give an online algorithm without lookahead that constructs schedules with a nearly optimal makespan of C_max^OPT+, for any >0, if at any time at least one machine is available. Our results demonstrate that not knowing machine availabilities in advance is of little harm.     

带重入的单台机排序问题

本文考虑带重入的单台机排序问题,重入是指每个工件在机器上加工不止一次.通过把重入模型转化为带平行链约束的排序问题,我们成功地获得了单机重入问题的两个目标函数的多项式时间最优算法,一个是总带权完工时间∑ωjCj,另一个是最大费用函数hmax.     

Pairs of codes with prescribed Hamming distances and coincidences

The main problem of coding theory is to construct codes with large Hamming-distances between the code-words. In this work we describe a fast algorithm for generating pairs of q-ary codes with prescribed pairwise Hamming-distances and coincidences (for a letter s ∈ {0,1,...,q − 1}, the number of s-coincidences between codewords a and b is the number of letters s in the same positions both in a and b). The method is a generalization of a method for constructing set-systems with prescribed intersection sizes (Grolmusz (2002) Constructing set-systems with prescribed intersection sizes. J Algorithms 44:321–337), where only the case q = 2 and s = 1 was examined. As an application, we show that the modular version of the classical Delsarte-inequality does not hold for odd, non-prime power composite moduli.      

Prediction of Euclidean distances with discrete and continuous outcomes

The objective of this paper is first to predict generalized Euclidean distances in the context of discrete and quantitative variables and then to derive their statistical properties. We first consider the simultaneous modelling of discrete and continuous random variables with covariates and obtain the likelihood. We derive an important property useful for its practical maximization. We then study the prediction of any Euclidean distances and its statistical proprieties, especially for the Mahalanobis distance. The quality of distance estimation is analyzed through simulations. This results are applied to our motivating example: the official distinction procedure of rapeseed varieties.