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

作者： Cai, Xingyu University of Connecticut

学位级别：Ph.D., Doctor of Philosophy

The Closest Pair problem aims to identify the closest pair (using some similarity measure, e.g., Euclidean distance, Dynamic Time Warping distance, etc.) of points in a metric space. This is one of the fundamental problems that has a wide range of applications in the data mining area, since most of the data can be represented in a vector form residing in a high dimensional space, and we would like to identify the relationship among those data points. Typical applications include but not limited to, social data analysis, user pattern identification, motif mining in biological data, data clustering, etc. This is a very classical problem and has been studied very well in the past *** this thesis, we study the Closest Pair problem and its variants, and also bring the machine learning perspective to solve some closely related problems. In particular, we have proposed two approximate algorithms to efficiently address the Closest Pair of Points (CPP) problem, and one deterministic approach to solve the Closest Pair of Subsequences (CPS) problem, using Euclidean distance measure. In addition, to identify the closest subsequences in the time series data, we have proposed a learnable feature extractor embedded in an artificial neural network, to learn patterns in the scope of the Dynamic Time Warping metric. In the end, to speed up the inference speed of the proposed algorithm, we have also proposed a neural network pruning technique to obtain a smaller network with similar *** the proposed methods are shown to have achieved the state-of-the-art performance in various standard benchmark datasets.

关键词： Closest Pair Approximate algorithm deterministic algorithm Dynamic Time Warping Neural Network

来源：评论

学校读者我要写书评

暂无评论

A symmetry-driven BP algorithm for the Discretizable Molecular Distance Geometry Problem

A symmetry-driven BP algorithm for the Discretizable Molecul...

引用

IEEE International Conference on Bioinformatics and Biomedicine Workshops (BIBMW)

作者： Mucherino, A. Lavor, C. Liberti, L. Univ Rennes 1 IRISA Rennes France Univ Estadual Campinas IMECC Campinas SP Brazil Ecole Polytech LIX Palaiseau France

ISBN: (纸本)9781457716133

Branch & Prune (BP) is a deterministic algorithm for the solution of the Discretizable Molecular Distance Geometry Problem (DMDGP). This problem has important applications in the field of structural biology, in particular for the determination of the three-dimensional conformation of a molecule by using information obtained by NMR techniques. In recent works, we proved that the search domain of the DMDGP, which is represented by a binary tree, contains various symmetries which are related to the number of solutions to the problem. In the present work, we propose a variant of the BP algorithm which is able to exploit the information regarding the symmetries to speed up the search. Computational experiments show that the symmetry-driven BP (symBP) outperforms the original BP algorithm in particular when instances having several solutions are considered.

关键词： Atomic layer deposition Atomic measurements Binary trees Conferences Geometry NMR imaging NMR techniques Nuclear magnetic resonance Proteins binary tree biology computing branch & prune algorithm computational geometry deterministic algorithm discretizabl

来源：评论

学校读者我要写书评

暂无评论

Computing Static Schedule for the Hosts in a Real-Time Distributed System with Component Based Applications 9

Computing Static Schedule for the Hosts in a Real-Time Distr...

引用

9th Int Conf Ind Information Syst (ICIIS2014)

作者： Canute, Julius Kumar, Atul IIIT Bangalore Karnataka India Siemens Corp Res & Technol Bangalore Karnataka India ABB Corp Res Bangalore Karnataka India

ISBN: (纸本)9781479964994

We consider cyclic real-time applications built using nearly autonomous components. These components can run on any of the available hosts subject to certain constraints. The hosts in the system are allowed to be heterogeneous and they can have different cycle times for real time execution. Given a set of component based applications and a set of available hosts, we propose a solution for the problem of finding an optimum deployment. The deployment problem can be reduced to the problem of finding feasible static schedules for each host in the system that satisfy the real-time periodic execution requirements of all the applications. We propose a deterministic algorithm for finding static schedules for all the hosts in the system. The approach models the possible partial schedules at each step as nodes in a virtual tree. A breadth first traversal is conducted to construct the tree and complete the schedule. A node is removed from the tree if it cannot lead to a correct schedule. If more than one solutions are possible then the 'best' solution is selected based on the optimization criteria.

关键词： distributed processing object-oriented programming optimisation trees (mathematics) breadth first traversal component based applications cyclic real-time applications deployment problem deterministic algorithm nearly autonomous components optimization criteria partial schedules real time execution real-time distributed system static schedule computation virtual tree Complexity theory Electronic mail Optimization Real-time systems Resource management Schedules Software optimal criterion deterministic algorithms real-time systems hosts electronic mail Distributed processing Complexity theory object oriented programming management of resources computer software time cycles Real time

来源：评论

学校读者我要写书评

暂无评论

Tradeoffs between Cost and Information for Rendezvous and Treasure Hunt 18

Tradeoffs between Cost and Information for Rendezvous and Tr...

引用

18th International Conference on Principles of Distributed Systems (OPODIS)

作者： Miller, Avery Pelc, Andrzej Univ Quebec Outaouais Gatineau PQ Canada

ISBN: (纸本)9783319144726;9783319144719

Rendezvous and treasure hunt are two basic tasks performed by mobile agents in networks. In rendezvous, two agents, initially located at distinct nodes of the network, traverse edges in synchronous rounds and have to meet at some node. In treasure hunt, a single agent has to find a stationary target (treasure) situated at an unknown node. The network is modeled as an undirected connected graph whose nodes have distinct identities. The cost of a rendezvous algorithm is the worst-case total number of edge traversals performed by both agents until meeting. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until the treasure is found. If the agents have no information about the network, the cost of both rendezvous and treasure hunt can be as large as Theta(e) for networks with e edges. We study tradeoffs between the amount of information available a priori to the agents and the cost of rendezvous and treasure hunt. Following the paradigm of algorithms with advice, this information is provided to the agents at the start of their navigation by an oracle knowing the network, the starting positions of the agents, and, in the case of treasure hunt, the node where the treasure is hidden. The oracle assists the agents by providing them with a binary string called advice, which can be used by each agent during the algorithm execution. In the case of rendezvous, the advice given to each agent can be different. The length of the string given to the agent in treasure hunt and the sum of the lengths of strings given to the agents in rendezvous is called the size of advice. Our goal is to find the smallest size of advice which enables the agents to solve rendezvous and treasure hunt at a given cost C in a network with e edges. This size turns out to depend on the initial distance D and on the ratio g = e/C, which is the relative cost gain due to advice. For arbitrary graphs, we give upper and lower bounds of O(Dlog(Dg)) and Omeg

关键词： rendezvous treasure hunt advice deterministic algorithm mobile agent cost

来源：评论

学校读者我要写书评

暂无评论

Fixed Outline Multi-Bend Bus Driven Floorplanning

Fixed Outline Multi-Bend Bus Driven Floorplanning

引用

11th International Symposium on Quality Electronic Design (ISQED)

作者： Sheng, Wenxu Dong, Sheqin Wu, Yuliang Goto, Satoshi Tsinghua Univ Tsinghua Natl Lab Informat Sci & Technol Beijing 100084 Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China Waseda Univ Informat Prod & Syst Kitakyushu Fukuoka 8080135 Japan

ISBN: (纸本)9781424464555

Modern hierarchical SOC design flows need to deal with fixed-outline floorplanning under the interconnect constraints, in this paper, we address the problem of bus driven floorplanning in a fixed-outline area. Given a set of blocks, the bus specification, and the height and width of the chip area, a floorplan solution including bus routes and satisfying the outline constraint will be generated with the total floorplan area and total bus area minimized The approach proposed in this paper is based on a deterministic algorithm Less Flexibility First (LFF), which runs in a fixed outline area and packs hard blocks one after another with no drawbacks. In our approach, we put no limitation to the shape of the buses, and the processes block-packing and bus packing are proceeding simultaneously. Experiment results show that under the constraint of fixed-outline, we can also obtain a good solution, with less dead space percentage and shorter run time, besides, for large test cases, our algorithm still works well.

关键词： Bus planning Fixed outline deterministic algorithm Floorplanning

来源：评论

学校读者我要写书评

暂无评论

Want to Gather? No Need to Chatter! 20

Want to Gather? No Need to Chatter!

引用

39th Symposium on Principles of Distributed Computing

作者： Bouchard, Sebastien Dieudonne, Yoann Pelc, Andrzej Univ Quebec Outaouais Gatineau PQ Canada Sorbonne Univ CNRS Inria LIP6 UMR 7606 Paris France Univ Picardie Jules Verne MIS Lab Amiens France

ISBN: (纸本)9781450375825

A team of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to meet at the same node and declare that they have all met. Agents have different labels which are positive integers, and move in synchronous rounds along links of the network. The above task is known as gathering and was traditionally considered under the assumption that when some agents are at the same node then they can talk, i.e., exchange currently available information. In this paper we ask the question of whether this ability of talking is needed for gathering. The answer turns out to be no. Our main contribution are two deterministic algorithms that always accomplish gathering in a much weaker model. We only assume that at any time an agent knows how many agents are at the node that it currently occupies but agents do not see the labels of other co-located agents and cannot exchange any information with them. They also do not see other nodes than the current one. Our first algorithm works under the assumption that agents know a priori some upper bound N on the size of the network, and it works in time polynomial in N and in the length l of the smallest label. Our second algorithm does not assume any a priori knowledge about the network but its complexity is exponential in the size of the network and in the labels of agents. Its purpose is to show feasibility of gathering under this harsher scenario. As a by-product of our techniques we obtain, in the same weak model, the solution of the fundamental problem of leader election among agents: One agent is elected a leader and all agents learn its identity. As an application of our result we also solve, in the same model, the well-known gossiping problem: if each agent has a message at the beginning, we show how to make all messages known to all agents, even without any a priori knowledge about the network. If agents know an upper bound N on the size of the network then our gossiping algorithm works in

关键词： gathering deterministic algorithm anonymous mobile agent

来源：评论

学校读者我要写书评

暂无评论

Online advertising assignment problem without free disposal

引用

APPLIED SOFT COMPUTING 2020年 93卷 106370-106370页

作者： Kim, Gwang Moon, Ilkyeong Seoul Natl Univ Dept Ind Engn 1 Gwanak Ro Seoul South Korea Seoul Natl Univ Inst Ind Syst Innovat 1 Gwanak Ro Seoul South Korea

This paper presents an online advertising assignment problem that generalizes the online version of the bipartite matching problem. Specifically, it focuses on the Display Ads problem, which is a generalization of the edge-weighted and capacitated matching problem. The display ads problem has been studied alongside the property of free disposal, in which an advertisement is allowed to be matched more times than its capacity. Although the problem with free disposal is tractable, the problem situation might be restricted and challenging to apply to other types of problems. The objective of this research on the display ads problem is to maximize the total weight of matched edges while considering a strict capacity constraint. This paper analyzes two online input orders (adversarial and probabilistic orders) to the problem. For the adversarial order, we design deterministic algorithms with worst-case guarantees and prove the competitive ratios of them. Upper bounds for the problem are also proposed. For the probabilistic order, stochastic online algorithms, consisting of scenario-based stochastic programming and Benders decomposition, are presented. We conduct numerical experiments of the stochastic online algorithm in two probabilistic order models (known IID and random permutation). (C) 2020 Elsevier B.V. All rights reserved.

关键词： Online bipartite matching Online algorithms deterministic algorithm Stochastic programming Benders decomposition

来源：评论

学校读者我要写书评

暂无评论

Collaborative dispersion by silent robots

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2024年 188卷

作者： Gorain, Barun Mandal, Partha Sarathi Mondal, Kaushik Pandit, Supantha Indian Inst Technol Bhilai Chhattisgarh India Indian Inst Technol Guwahati Gauhati India Indian Inst Technol Ropar Rupnagar Punjab India Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar Gujarat India

In the dispersion problem, a set of k co -located mobile robots must relocate themselves in distinct nodes of an unknown network. The network is modeled as an anonymous graph G = (V, E), where the graph's nodes are not labeled. The edges incident to a node v with degree d are labeled with port numbers in the range {0, 1, ..., d -1} at v. The robots have unique IDs in the range [0, L], where L >= k, and are initially placed at a source node s. The task of the dispersion was traditionally achieved based on the assumption of two types of communication abilities: (a) when some robots are at the same node, they can communicate by exchanging messages between them, and (b) any two robots in the network can exchange messages between them. This paper investigates whether this communication ability among co -located robots is absolutely necessary to achieve dispersion. We establish that even in the absence of the ability of communication, the task of the dispersion by a set of mobile robots can be achieved in a much weaker model, where a robot at a node v has access to following very restricted information at the beginning of any round: (1) am I alone at v? (2) did the number of robots at v increase or decrease compared to the previous round? We propose a deterministic distributed algorithm that achieves the dispersion on any given graph G = (V, E) in time O (k log L + k2 log A), where A is the maximum degree of a node in G. Further, each robot uses O(log L + log A) additional memory, i.e., memory other than the memory required to store its id. We also prove that the task of the dispersion cannot be achieved by a set of mobile robots with o(log L + log A) additional memory.

关键词： Mobile robots Anonymous graphs Dispersion deterministic algorithm Time and memory complexity

来源：评论

学校读者我要写书评

暂无评论

A Non-Parameter Filled Function Method for Unconstrained Global Optimization Problems

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2024年第2期41卷 2350013-2350013页

作者： Liu, Yingchun Gao, Yuelin Ma, Suxia Guo, Eryang North Minzu Univ Sch Math & Informat Sci Yinchuan 750021 Peoples R China North Minzu Univ Ningxia Prov Cooperat Innovat Ctr Sci Comp & Intel Yinchuan 750021 Peoples R China

In the paper, we give a new non-parameter filled function method for finding global minimizer of global optimization programming problems, the filled function consists of a inverse cosine function and a logarithm function, and without parameter. Its theoretical residences are proved. A new filled function algorithm is given based on the proposed new parameterless filled function, The results of numerical with ten experiments verify the efficient and reliability for the algorithm.

关键词： Global optimization problems filled function deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

A further study on weak Byzantine gathering of mobile agents

引用

THEORETICAL COMPUTER SCIENCE 2024年 1022卷

作者： Saxena, Ashish Mondal, Kaushik Indian Inst Technol Ropar Dept Math Rupnagar 140001 Punjab India

The gathering of mobile agents in the presence of Byzantine faults is first studied by Dieudonn & eacute;et al. Authors provide a polynomial time algorithm handling any number of weak Byzantine agents in the presence of at least one good agent considering start-up delays, i.e., the good agents may not wake up at the same time. Hirose et al. [1] come up with an algorithm considering start-up delays that use a strong team of at least 4f (2 )+ 8f + 4 many good agents but runs much faster than that of Dieudonn & eacute;et al. Later, Hirose et al. [2] provided another polynomial time algorithm for gathering in the presence of at least 7f + 7 good agents. This algorithm works considering start-up delay and achieves simultaneous termination. However, this algorithm depends on the length of the largest ID in the system. We, in this work, provide an algorithm considering start-up delays of the good agents, reducing the number of good agents w.r.t. [1] to f(2) agents achieve simultaneous termination. Our algorithm runs faster than [2] when the ID range of the good agents is significantly smaller in comparison to the ID range of all the agents. We also provide a much faster O(n(2)) time algorithm for trees using 3f + 2 agents handling start-up delays and guaranteeing simultaneous termination on a restricted ID range.

关键词： Mobile agents Anonymous graphs Gathering Byzantine faults deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：