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

Approximate and randomized algorithms for Computing a Second Hamiltonian Cycle

algorithmICA 2024年第9期86卷 2766-2785页

作者： Deligkas, Argyrios Mertzios, George B. Spirakis, Paul G. Zamaraev, Viktor Royal Holloway Univ London Dept Comp Sci Egham England Univ Durham Dept Comp Sci Durham England Univ Liverpool Dept Comp Sci Liverpool England

In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle C 'not equal CofG, and if yes, how quickly? If the input graph G satisfies certain conditions (e.g. if every vertex of G is odd, or if the minimum degree is large enough), it is known that such a second Hamiltonian cycle always exists. Despite substantial efforts, no subexponential-time algorithm is known for this problem. In this paper we relax the problem of computing a second Hamiltonian cycle in two ways. First, we consider approximating the length of a second longest cycle on n vertex graphs with minimum degree delta and maximum degree Delta. We provide a linear-time algorithm for computing a cycle C 'not equal C of length at least n-4 alpha(root n+2 alpha)+8, where alpha = Delta-2 / delta-2. This results provides a constructive proof of a recent result by Girao, Kittipassorn, and Narayanan in the regime of Delta/delta = o(root n). Our second relaxation of the problem is *** propose a randomized algorithm which computes a second Hamiltonian cycle with high probability, given that the input graph G has a large enough minimum degree. More specifically, we prove that for every 0< p <= 0.02, if the minimum degree of G is at least 8 / p log root 8n + 4, then a second Hamiltonian cycle can be computed with probability at least 1-1 / n(50/p(4)+1)in poly (n)2(4pn )time. This result implies that, when the minimum degree delta is sufficiently large, we can compute with high probability a second Hamiltonian cycle faster than any known deterministic algorithm. In particular,when delta = omega(log n), our probabilistic algorithm works in 2(o(n) )time.

关键词： Hamiltonian cycle Graph with minimum degree 3 Approximation algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Energy Management Strategy for EV Charging Stations Using randomized algorithms

引用

IEEE TRANSACTIONS ON CONTROL SYSTEMS TECHNOLOGY 2018年第3期26卷 1099-1106页

作者： Pflaum, Peter Alamir, Mazen Lamoudi, Mohamed Yacine Schneider Elect Ind F-38000 Grenoble France Domaine Univ Univ Grenoble CNRS F-38400 St Martin Dheres France

Electric vehicle charging stations (EVCSs) come along with great challenges for the power grid due to their highly uncertain load characteristic. This is particularly the case for charging stations located in nonresidential areas, such as commercial centers, company sites, or car-rental stations. For a safe and sustainable operation of the power grid, distribution system operators require reliable load forecasts of such charging stations. In this brief, a robust EVCS management strategy is proposed, which provides a day-ahead upper limit profile of the EVCS's power consumption. In real time, this upper limit profile is strictly respected while guaranteeing-at a configurable probability-the Quality of Service. The strategy is based on randomized algorithms and relies on a statistic occupancy model of the EVCS while not requiring any online forecasts of each EVs' arrival and departure schedules. In a case study based on statistic data, which has been provided by the Euref Campus in Berlin, the feasibility and relevance of the proposed approach are demonstrated.

关键词： Electric vehicle charging station (EVCS) energy management optimization randomized algorithm statistic EV behavior model

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT randomized algorithmS FOR THE FIXED-PRECISION LOW-RANK MATRIX APPROXIMATION

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2018年第3期39卷 1339-1359页

作者： Yu, Wenjian Gu, Yu Li, Yaohang Tsinghua Univ BNRist Dept Comp Sci & Technol Beijing 100084 Peoples R China Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China Old Dominion Univ Dept Comp Sci Norfolk VA 23529 USA

randomized algorithms for low-rank matrix approximation are investigated, with the emphasis on the fixed-precision problem and computational efficiency for handling large matrices. The algorithms are based on the so-called QB factorization, where Q is an orthonormal matrix. First, a mechanism for calculating the approximation error in the Frobenius norm is proposed, which enables efficient adaptive rank determination for a large and/or sparse matrix. It can be combined with any QB-form factorization algorithm in which B's rows are incrementally generated. Based on the blocked randQB algorithm by Martinsson and Voronin, this results in an algorithm called randQB_EI. Then, we further revise the algorithm to obtain a pass-efficient algorithm, randQB_FP, which is mathematically equivalent to the existing randQB algorithms and also suitable for the fixed-precision problem. Especially, randQB_FP can serve as a single-pass algorithm for calculating leading singular values, under a certain condition. With large and/or sparse test matrices, we have empirically validated the merits of the proposed techniques, which exhibit remarkable speedup and memory saving over the blocked randQB algorithm. We have also demonstrated that the single-pass algorithm derived by randQB_FP is much more accurate than an existing single-pass algorithm. And with data from a scenic image and an information retrieval application, we have shown the advantages of the proposed algorithms over the adaptive range finder algorithm for solving the fixed-precision problem.

关键词： adaptive rank determination randomized algorithm low-rank matrix approximation pass-efficient algorithm fixed-precision problem

来源：评论

学校读者我要写书评

暂无评论

Logarithmic Weighted Random Selector algorithm: A Novel Approach for Biasing Selection Based on Positional Order Without Hyperparameters 17th

Logarithmic Weighted Random Selector Algorithm: A Novel Appr...

引用

17th Workshop of Hybrid Intelligent Systems, HIS 2024, 17th Workshop on Intelligent Learning Environments, WILE 2024 and 6th Workshop on New Trends in Computational Intelligence and Applications, CIAPP 2024, held in conjunction with Mexican International Conference on Artificial Intelligence, MICAI 2024

作者： Ramos Herrera, Iván Alejandro Autonomous University of Aguascalientes Aguascalientes Mexico

ISBN: (纸本)9783031838781

The "Logarithmic Weighted Random Selector" (LWRS) introduces a novel algorithm designed for selecting randomly one item from a list, with the bias that the further to the beginning of the list each one is, the more likely it is to be selected. Unlike traditional selection and sampling methods that rely on numerical fitness scores or require hyperparameter tuning, LWRS employs a logarithmic weighting mechanism to naturally favor items based on their position. It arose from the problem of requiring a method that allows weighting a selection based on the order of preference on a list of elements, for phenomena for which numerical weighting values are unknown but only their order, which unlike algorithms such as Rank-based Selection, does not require configuration of hyperparameters. Different mechanisms were explored, such as a Linear Selection method and Exponential Selection. Discovering that utilizing a logarithmic scale, LWRS achieves a non-numerical preference bias, distinguishing itself from classic methods of weighted random sampling as Fitness-proportionate selection and Tournament Selection, which do require defined numerical weights, contributing to the field with a straightforward, parameter-free approach to weighted random selection. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： algorithm Design Computer Science Evolutionary Computing Random Sampling randomized algorithm Selection Method

来源：评论

学校读者我要写书评

暂无评论

randomized probe selection algorithm for microarray design

引用

JOURNAL OF THEORETICAL BIOLOGY 2007年第3期248卷 512-521页

作者： Gasieniec, Leszek Li, Cindy Y. Sant, Paul Wong, Prudence W. H. Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

DNA microarray technology, originally developed to measure the level of gene expression, has become one of the most widely used tools in genomic study. The crux of microarray design lies in how to select a unique probe that distinguishes a given genomic sequence from other sequences. Due to its significance, probe selection attracts a lot of attention. Various probe selection algorithms have been developed in recent years. Good probe selection algorithms should produce a small number of candidate probes. Efficiency is also crucial because the data involved are usually huge. Most existing algorithms are usually not sufficiently selective and quite a large number of probes are returned. We propose a new direction to tackle the problem and give an efficient algorithm based on randomization to select a small set of probes and demonstrate that such a small set of probes is sufficient to distinguish each sequence from all the other sequences. Based on the algorithm, we have developed probe selection software RANDPS, which runs efficiently in practice. The software is available on our website (http://***/similar to cindy/RandPS/***). We test our algorithm via experiments on different genomes (Escherichia coli, Saccharamyces cercvisiae, etc.) and our algorithm is able to output unique probes for most of the genes efficiently. The other genes can be identified by a combination of at most two probes. (C) 2007 Elsevier Ltd. All rights reserved.

关键词： randomized algorithm probe selection microarray design

来源：评论

学校读者我要写书评

暂无评论

New parallel randomized algorithms for the traveling salesman problem

引用

COMPUTERS & OPERATIONS RESEARCH 1999年第4期26卷 371-394页

作者： Shi, LY Olafsson, S Sun, N Univ Wisconsin Dept Ind Engn Madison WI 53706 USA

We recently developed a new randomized optimization framework, the Nested Partitions (NP) method. This approach uses partitioning, global random sampling, and local search heuristics to create a Markov chain that has global optima as its absorbing states. This new method combines global and local search in a natural way and it is highly matched to emerging massively parallel processing capabilities. In this paper, we apply the NP method to the Travelling Salesman Problem. Preliminary numerical results show that the NP method generates high-quality solutions compared to well-known heuristic methods, and that it can be a very promising alternative for finding a solution to the TSP. (C) 1999 Elsevier Science Ltd. All rights reserved.

关键词： optimization randomized algorithm parallel algorithm traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

HYPERMEDIA AND randomized algorithmS FOR MEDICAL EXPERT SYSTEMS

引用

COMPUTER METHODS AND PROGRAMS IN BIOMEDICINE 1990年第1期32卷 5-16页

作者： CHAVEZ, RM COOPER, GF Section on Medical Informatics Stanford University School of Medicine CA 94305.

KNET is an environment for constructing probabilistic, knowledge-intensive systems within the axiomatic framework of decision theory. The KNET architecture defines a complete separation between the hypermedia user interface on the one hand, and the representation and management of expert opinion on the other. KNET offers a choice of algorithms for probabilistic inference. We and our coworkers have used KNET to build consultation systems for lymph-node pathology, bone-marrow transplantation therapy, clinical epidemiology, and alarm management in the intensive-care unit. Most important, KNET contains a randomized approximation scheme (RAS) for the difficult and almost certainly intractable problem of Bayesian inference. Our algorithm can, in many circumstances, perform efficient approximate inference in large and richly interconnected models of medical diagnosis. In this article, we describe the architecture of KNET, construct a randomized algorithm for probabilistic inference, and analyze the algorithm's performance. Finally, we characterize our algorithms' empiric behavior and explore its potential for parallel speedups. From design to implementation, then, KNET demonstrates the crucial interaction between theoretical computer science and medical informatics.

关键词： Probabilistic expert system Computational complexity theory randomized algorithm Medical informatics

来源：评论

学校读者我要写书评

暂无评论

randomized Pattern Formation algorithm for Asynchronous Oblivious Mobile Robots 28

Randomized Pattern Formation Algorithm for Asynchronous Obli...

引用

28th International Symposium on Distributed Computing

作者： Yamauchi, Yukiko Yamashita, Masafumi Kyushu Univ Fac Informat Sci & Elect Engn Fukuoka 812 Japan

ISBN: (纸本)9783662451748

We present a randomized pattern formation algorithm for asynchronous oblivious (i.e., memory-less) mobile robots that enables formation of any target pattern. As for deterministic pattern formation algorithms, the class of patterns formable from an initial configuration I is characterized by the symmetricity (i.e., the order of rotational symmetry) of I, and in particular, every pattern is formable from I if its symmetricity is 1. The randomized pattern formation algorithm psi(PF) we present in this paper consists of two phases: The first phase transforms a given initial configuration I into a configuration I' such that its symmetricity is 1, and the second phase invokes a deterministic pattern formation algorithm psi(CWM) by Fujinaga et al. (DISC 2012) for asynchronous oblivious mobile robots to finally form the target pattern. There are two hurdles to overcome to realize psi(PF). First, all robots must simultaneously stop and agree on the end of the first phase, to safely start the second phase, since the correctness of psi(CWM) is guaranteed only for an initial configuration in which all robots are stationary. Second, the sets of configurations in the two phases must be disjoint, so that even oblivious robots can recognize which phase they are working on. We provide a set of tricks to overcome these hurdles.

关键词： Mobile robot pattern formation randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A method for obtaining randomized algorithms with small tail probabilities

引用

algorithmICA 1996年第4-5期16卷 543-547页

作者： Alt, H Guibas, L Mehlhorn, K Karp, R Wigderson, A STANFORD UNIV STANFORDCA 94305 DIGITAL EQUIPMENT CORP SYST RES CTRPALO ALTOCA 94301 UNIV SAARLAND MAX PLANCK INST INFORMATD-6600 SAARBRUCKENGERMANY UNIV SAARLAND FACHBEREICH INFORMATD-6600 SAARBRUCKENGERMANY INT COMP SCI INST BERKELEYCA 94704 UNIV CALIF BERKELEY BERKELEYCA 94720 HEBREW UNIV JERUSALEM DEPT COMP SCIIL-91905 JERUSALEMISRAEL PRINCETON UNIV DEPT COMP SCIPRINCETONNJ 07974

We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.

关键词： Las Vegas algorithms randomized algorithm tail probability

来源：评论

学校读者我要写书评

暂无评论

Node2binary: Compact Graph Node Embeddings using Binary Vectors 34

Node2binary: Compact Graph Node Embeddings using Binary Vect...

引用

34th ACM Web Conference, WWW 2025

作者： Talukder, Niloy Gyurek, Croix Al Hasan, Mohammad Indiana University Indianapolis Indianapolis IN United States University of Waterloo Waterloo ON Canada

ISBN: (纸本)9798400712746

With the adoption of deep learning models to low-power, small-memory edge devices, energy consumption and storage usage of such models have become a key concern. The problem exacerbates even further with ever-growing data and equally-matched bulkier models. This concern is particularly pronounced for graph data due to its quadratic storage, irregular (non-grid) geometry, and very large size. Typical graph data, such as road networks, infrastructure networks, and social networks, easily exceeds millions of nodes, and several gigabytes of storage is needed just to store the node embedding vectors, let alone the model parameters. In recent years, the memory issue has been addressed by moving away from memory-intensive double precision floating-point arithmetic towards single-precision or even half-precision, often by trading-off marginally small performance. Along this effort, we propose Node2binary, which embeds graph nodes in as few as 128 binary bits, thereby reducing the memory footprint of vertex embedding vectors by several orders of magnitude. Node2binary leverages a fast community detection algorithm to convert the given graph into a hierarchical partition tree and then find embeddings of graph vertices in binary space by solving a combinatorial optimization (CO) task over the tree edges. CO is NP-hard, but Node2binary uses an innovative combination of discrete gradient descent and randomization to solve this task effectively and efficiently. Extensive experiments over four real-world graphs show that Node2binary achieves competitive performance compared to the state-of-the art graph embedding methods in both node classification and link prediction tasks. © 2025 Copyright held by the owner/author(s).

关键词： Binary Space Embedding Discrete Gradient Descent Graph Embedding randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：