检索结果-内蒙古大学图书馆

2010 IEEE 51st Annual Symposium on Foundations of Computer Science

作者： Bansal, Nikhil IBM TJ Watson Res Ctr Yorktown Hts NY 10598 USA

ISBN: (纸本)9780769542447

Given a set system (V, S), V = {1, ..., n} and S = {S-1, ..., S-m}, the minimum discrepancy problem is to find a 2-coloring X : V --> {-1, +1}, such that each set is colored as evenly as possible, i.e. find X to minimize max(j is an element of[m]) vertical bar Sigma(i is an element of Sj) X(i)vertical bar. In this paper we give the first polynomial time algorithms for discrepancy minimization that achieve bounds similar to those known existentially using the so-called Entropy Method. We also give a first approximation-like result for discrepancy. Specifically we give efficient randomized algorithms to: 1) Construct an O(n(1/2)) discrepancy coloring for general sets systems when m = O(n), matching the celebrated result of Spencer [17] up to O(1) factors. More generally, for m >= n, we obtain a discrepancy of O(n(1/2) log (2m/n)). 2) Construct a coloring with discrepancy O (t(1/2) log n), if each element lies in at most t sets. This matches the (non-constructive) result of Srinivasan [19]. 3) Construct a coloring with discrepancy O(lambda log (nm)), where lambda is the hereditary discrepancy of the set system. The main idea in our algorithms is to produce a coloring over time by letting the color of the elements perform a random walk (with tiny increments) starting from 0 until they reach +/-1. At each step the random hops for various elements are correlated by a solution to a semidefinite program, where this program is determined by the current state and the entropy method.

关键词： Discrepancy Theory constructive algorithms

来源：评论

学校读者我要写书评

暂无评论

An analysis of constructive algorithms for the airport baggage sorting station assignment problem

引用

JOURNAL OF SCHEDULING 2014年第6期17卷 601-619页

作者： Asco, Amadeo Atkin, Jason A. D. Burke, Edmund K. Univ Nottingham Sch Comp Sci Nottingham NG7 2RD England Univ Stirling Dept Comp & Math Stirling FK9 4LA Scotland

The assignment of airport resources can significantly affect the quality of service provided by airlines and airports. High quality assignments can support airlines and airports in adhering to published schedules by minimising changes or delays while waiting for resources to become available. In this paper, we consider the problem of assigning available baggage sorting stations to flights which have already been scheduled and allocated to stands. A model for the problem is presented, and the different objectives which have to be considered are highlighted. A number of constructive algorithms for sorting station assignments are then presented and their effects are compared and analysed when different numbers of sorting stations are available. It can be observed that appropriate algorithm selection is highly dependent upon whether or not reductions in service time are permitted and upon the flight density in relation to the number of sorting stations. Finally, since these constructive approaches produce different solutions which are better for different trade-offs of the objectives, we utilise these as initial solutions for an evolutionary algorithm as well as for an Integer Linear Programming model in CPLEX. We show that in both cases they are helpful for improving the results which are obtainable within reasonable solution times.

关键词： Airport baggage sorting stations Scheduling Heuristics constructive algorithms Greedy algorithms

来源：评论

学校读者我要写书评

暂无评论

A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria

引用

COMPUTERS & OPERATIONS RESEARCH 2009年第2期36卷 358-378页

作者： Jungwattanakit, Jitti Reodecha, Manop Chaovalitwongse, Paveena Werner, Frank Otto Von Guericke Univ Fac Math D-39016 Magdeburg Germany Chulalongkorn Univ Fac Engn Dept Ind Engn Bangkok 10330 Thailand

This paper considers a flexible flow shop scheduling problem, where at least one production stage is made up of unrelated parallel machines. Moreover, sequence- and machine-dependent setup times are given. The objective is to find a schedule that minimizes a convex sum of makespan and the number of tardy jobs in a static flexible flow shop environment. For this problem, a 0-1 mixed integer program is formulated. The problem is, however, a combinatorial optimization problem which is too difficult to be solved optimally for large problem sizes, and hence heuristics are used to obtain good solutions in a reasonable time. The proposed constructive heuristics for sequencing the jobs start with the generation of the representatives of the operating time for each operation. Then some dispatching rules and flow shop makespan heuristics are developed. To improve the solutions obtained by the constructive algorithms, fast polynomial heuristic improvement algorithms based on shift moves and pairwise interchanges of jobs are applied. In addition, metaheuristics are suggested, namely simulated annealing (SA), tabu search (TS) and genetic algorithms. The basic parameters of each metaheuristic are briefly discussed in this paper. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages and with an optimal solution for small-size problems. We have found that among the constructive algorithms the insertion-based approach is superior to the others, whereas the proposed SA algorithms are better than TS and genetic algorithms among the iterative metaheuristic algorithms. (C) 2007 Elsevier Ltd. All rights reserved.

关键词： Flexible flow shop constructive algorithms Simulated annealing Tabu search Genetic algorithms

来源：评论

学校读者我要写书评

暂无评论

Bio-inspired machine learning: programmed death and replication

引用

NEURAL COMPUTING & APPLICATIONS 2023年第27期35卷 20273-20298页

作者： Grabovsky, Andrey Vanchurin, Vitaly Budker Inst Nucl Phys Novosibirsk 630090 Russia Novosibirsk State Univ Novosibirsk 630090 Russia Natl Ctr Biotechnol Informat NIH Bethesda MD 20894 USA Duluth Inst Adv Study Duluth MN 55804 USA

We analyze algorithmic and computational aspects of biological phenomena, such as replication and programmed death, in the context of machine learning. We use two different measures of neuron efficiency to develop machine learning algorithms for adding neurons to the system (i.e., replication algorithm) and removing neurons from the system (i.e., programmed death algorithm). We argue that the programmed death algorithm can be used for compression of neural networks and the replication algorithm can be used for improving performance of the already trained neural networks. We also show that a combined algorithm of programmed death and replication can improve the learning efficiency of arbitrary machine learning systems. The computational advantages of the bio-inspired algorithms are demonstrated by training feedforward neural networks on the MNIST dataset of handwritten images.

关键词： Machine learning Neural networks Bio-inspired algorithms Neuron correlations Pruning algorithms constructive algorithms Classification

来源：评论

学校读者我要写书评

暂无评论

An accelerating scheme for destructive parsimonious extreme learning machine

引用

NEUROCOMPUTING 2015年 167卷 671-687页

作者： Zhao, Yong-Ping Li, Bing Li, Ye-Bo Nanjing Univ Sci & Technol Sch Mech Engn Nanjing 210094 Jiangsu Peoples R China AVIC Aeroengine Control Res Inst Wuxi 214063 Peoples R China

constructive and destructive parsimonious extreme learning machines (CP-ELM and DP-ELM) were recently proposed to sparsify ELM. In comparison with CP-ELM, DP-ELM owns the advantage in the number of hidden nodes, but it loses the edge with respect to the training time. Hence, in this paper an equivalent measure is proposed to accelerate DP-ELM (ADP-ELM). As a result, ADP-ELM not only keeps the same hidden nodes as DP-ELM but also needs less training time than CP-ELM, which is especially important for the training time sensitive scenarios. The similar idea is extended to regularized ELM (RELM), yielding ADP-RELM. ADP-RELM accelerates the training process of DP-RELM further, and it works better than CP-RELM in terms of the number of hidden nodes and the training time. In addition, the computational complexity of the proposed accelerating scheme is analyzed in theory. From reported results on ten benchmark data sets, the effectiveness and usefulness of the proposed accelerating scheme in this paper is confirmed experimentally. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Single-hidden layer feedforward network Extreme learning machine Destructive algorithm constructive algorithms Sparseness

来源：评论

学校读者我要写书评

暂无评论

Geometrical synthesis of MLP neural networks

引用

NEUROCOMPUTING 2008年第4-6期71卷 919-930页

作者： Delogu, Rita Fanni, Alessandra Montisci, Augusto Univ Cagliari DIEE I-09123 Cagliari Italy

This paper presents a new constructive algorithm to design multilayer perceptron networks used its classifiers. The resulting networks are able to classify patterns defined in a real domain. The proposed procedure allows us to automatically determine both the number of neurons and the synaptic weights of networks with a single hidden layer. The approach is based on linear programming. It avoids the typical local minima problems of error back propagation and assures convergence of the method. Furthermore, it will be shown in this paper that the presented procedure leads to single-hidden layer neural networks able to solve any problem in classifying a finite number of patterns. The performances of the proposed algorithm have been tested on some benchmark problems, and they have been compared with those of different approaches. (c) 2007 Elsevier B.V. All rights reserved.

关键词： constructive algorithms neural network synthesis linear programming pattern classification

来源：评论

学校读者我要写书评

暂无评论

The Analysis and the Representation of Balanced Complex Polytopes in 2D

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2009年第3期9卷 259-294页

作者： Vagnoni, Cristina Zennaro, Marino Univ Trieste Dipartimento Matemat & Informat I-34127 Trieste Italy Univ Padua Dipartimento Matemat Pura & Applicata I-35121 Padua Italy

In this paper, we deepen the theoretical study of the geometric structure of a balanced complex polytope (b.c.p.), which is the generalization of a real centrally symmetric polytope to the complex space. We also propose a constructive algorithm for the representation of its facets in terms of their associated linear functionals. The b.c.p.s are used, for example, as a tool for the computation of the joint spectral radius of families of matrices. For the representation of real polytopes, there exist well-known algorithms such as, for example, the Beneath-Beyond method. Our purpose is to modify and adapt this method to the complex case by exploiting the geometric features of the b.c.p. However, due to the significant increase in the difficulty of the problem when passing from the real to the complex case, in this paper, we confine ourselves to examine the two-dimensional case. We also propose an algorithm for the computation of the norm the unit ball of which is a b.c.p.

关键词： Balanced complex polytopes Polytope norms constructive algorithms

来源：评论

学校读者我要写书评

暂无评论

VCS: A new heuristic function for selecting boxes in the single container loading problem

引用

COMPUTERS & OPERATIONS RESEARCH 2017年 82卷 27-35页

作者： Araya, Ignacio Guerrero, Keitel Nunez, Eduardo Pontificia Univ Catolica Valparaiso Escuela Ingn Informat Avenida Brasil 2950 Vregion Chile

The single container loading problem consists of a container that has to be filled with a set of boxes. The objective of the problem is to maximize the total volume of the loaded boxes. For solving the problem, constructive approaches are the most successful. A key element of these approaches is related to the selection of the box to load next. In this work, we propose a new evaluation function for ranking boxes. Our function rewards boxes that fit well in the container, taking into account the previously placed ones. To construct a more robust function, we consider some other well-known evaluation criteria such as the volume of the block and the estimated wasted volume in the free space of the container. Our approach shows promising results when compared with other state-of-the-art algorithms on a set of 1600 well known benchmark instances. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Container loading problem Load planing Combinatorial optimization constructive algorithms Evaluation function

来源：评论

学校读者我要写书评

暂无评论

Objective functions for training new hidden units in constructive neural networks

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS 1997年第5期8卷 1131-1148页

作者： Kwok, TY Yeung, DY Department of Computer Science University of Science and Technology (HKUST) Kowloon Hong Kong China

In this paper, we study a number of objective functions for training new hidden units in constructive algorithms for multilayer feedforward networks. The aim is to derive a class of objective functions the computation of which and the corresponding weight updates can be done in O(N) time, where N is the number of training patterns. Moreover, even though. input weight freezing is applied during the process for computational efficiency, the convergence property of the constructive algorithms using these objective functions is still preserved. We also propose a few computational tricks that can be used to improve the optimization of the objective functions under practical situations. Their relative performance in a set of two-dimensional regression problems is also discussed.

关键词： cascade-correlation constructive algorithms convergence input weight freezing quickprop

来源：评论

学校读者我要写书评

暂无评论

SEPARATE: A machine learning method based on semi-global partitions

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS 2000年第3期11卷 710-720页

作者： Castro, JL Delgado, M Mantas, CJ Univ Granada Dept Comp Sci & Artificial Intelligence E-18071 Granada Spain

This article presents a machine learning method for solving classification and approximation problems. This method uses the divide-and-conquer algorithm design technique (taken from machine learning models based on a tree), with the aim of achieving design ease and good results on the training examples and allows semi-global actions on its computational elements (a feature taken from neural networks), with the aim of attaining good generalization and good behavior in the presence of noise in training examples. Finally, some results obtained after solving several problems with a particular implementation of SEPARATE are presented together with their analysis.

关键词： constructive algorithms divide-and-conquer neural networks

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：