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

Global algorithm for effectively solving min-max affine fractional programs

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2024年第2期70卷 1787-1811页

作者： Jiao, Hongwei Sun, Yudong Wang, Wenjie Shang, Youlin Henan Inst Sci & Technol Sch Math Sci Xinxiang 453003 Peoples R China Henan Univ Sci & Technol Sch Math & Stat Luoyang 471023 Peoples R China

This article investigates solving the min-max affine fractional programming problem (MAFPP), which arises in systems science and engineering. For globally solving the MAFPP, based on the outer space branching search, we design a branch-relaxation-bound algorithm. In the algorithm, we firstly convert the MAFPP into an equivalent problem with linear fractional constraints by introducing some auxiliary parameter variables. Next, to determine and update the lower bound during the branching search process, we construct the linear relaxation problem of the equivalence problem by using a new relaxation technique. The global convergence of the presented algorithm is verified. Also, by analyzing the algorithmic complexity, we give a maximum estimate of iteration times of the presented algorithm. Finally, computational comparison results are reported to demonstrate the effectiveness and feasibility of the presented algorithm.

关键词： Min-max affine fractional programs Linear relaxation technique Branch-relaxation-bound algorithm algorithmic complexity

来源：评论

学校读者我要写书评

暂无评论

On the complexity of Reasoning in Kleene Algebra with Commutativity Conditions 1

引用

20th International Colloquium on Theoretical Aspects of Computing (ICTAC)

作者： Kuznetsov, Stepan L. Steklov Math Inst RAS Moscow Russia

ISBN: (数字)9783031479632

ISBN: (纸本)9783031479625;9783031479632

Kleene algebras are one of the basic algebraic structures used in computer science, involving iteration, or Kleene star. An important subclass of Kleene algebras is formed by *-continuous ones. In his 2002 paper, Dexter Kozen pinpointed complexity of various logical theories for Kleene algebras, both in the general and in the *-continuous case. Those complexity results range from equational theories to Horn theories, or reasoning from hypotheses. In the middle, there are fragments of Horn theories, with restrictions on hypotheses. For the case when the hypotheses are commutativity conditions, i.e., commutation equations for designated pairs of atoms, however, Kozen mentioned the complexity result (Pi(0)(1)-completeness) only for the *-continuous case, while the general case remained an open question. This was the only gap in Kozen's table of results, and the present paper fills this gap. Namely, we prove that reasoning from commutativity conditions on the class of all Kleene algebras is Sigma(0)(1)-complete. In particular, this problem is undecidable.

关键词： Kleene algebra commutativity conditions algorithmic complexity

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for sorting by k-cuts on signed permutations

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-30页

作者： Oliveira, Andre Rodrigues Alexandrino, Alexsandro Oliveira Jean, Geraldine Fertin, Guillaume Dias, Ulisses Dias, Zanoni Univ Estadual Campinas Inst Comp Campinas SP Brazil Nantes Univ UMR LS2N CNRS F-6004 Nantes France Univ Estadual Campinas Sch Technol Limeira Brazil

Sorting by Genome Rearrangements is a classic problem in Computational Biology. Several models have been considered so far, each of them defines how a genome is modeled (for example, permutations when assuming no duplicated genes, strings if duplicated genes are allowed, and/or use of signs on each element when gene orientation is known), and which rearrangements are allowed. Recently, a new problem, called Sorting by Multi-Cut Rearrangements, was proposed. It uses the k-cut rearrangement which cuts a permutation (or a string) at k >= 2 places and rearranges the generated blocks to obtain a new permutation (or string) of same size. This new rearrangement may model chromoanagenesis, a phenomenon consisting of massive simultaneous rearrangements. Similarly as the Double-Cut-and-Join, this new rearrangement also generalizes several genome rearrangements such as reversals, transpositions, revrevs, transreversals, and block-interchanges. In this paper, we extend a previous work based on unsigned permutations and strings to signed permutations. We show the complexity of this problem for different values of k, and that the approximation algorithm proposed for unsigned permutations with any value of k can be adapted to signed permutations. We also show a 1.5-approximation algorithm for the specific case k = 4, as well as a generic approximation algorithm applicable for any k >= 5, that always reaches constant ratio. The latter makes use of the cycle graph, a well-known structure in genome rearrangements. We implemented and tested the proposed algorithms on simulated data.

关键词： Genome rearrangements Sorting permutations Approximation algorithms algorithmic complexity

来源：评论

学校读者我要写书评

暂无评论

Post-Quantum Cryptography (PQC) Network Instrument: Measuring PQC Adoption Rates and Identifying Migration Pathways 5

Post-Quantum Cryptography (PQC) Network Instrument: Measurin...

引用

2024 International Conference on Quantum Computing and Engineering

作者： Sowa, Jakub Hoang, Bach Yeluru, Advaith Qie, Steven Nikolich, Anita Iyer, Ravishankar Cao, Phuong Natl Ctr Supercomputing Applicat Urbana IL 61801 USA Univ Illinois Champaign IL USA

ISBN: (纸本)9798331541378

The problem of adopting quantum-resistant cryptographic network protocols or post-quantum cryptography (PQC) is critically important to democratizing quantum computing. The problem is urgent because practical quantum computers will break classical encryption in the next few decades. Past encrypted data has already been collected and can be decrypted in the near future. The main challenges of adopting post-quantum cryptography lie in algorithmic complexity and hardware/software/network implementation. The grand question of how existing cyberinfrastructure will support post-quantum cryptography remains unanswered. This paper describes: i) the design of a novel Post-Quantum Cryptography (PQC) network instrument placed at the National Center for Supercomputing Applications (NCSA) at the University of Illinois at Urbana-Champaign and a part of the FABRIC testbed;ii) the latest results on PQC adoption rate across a wide spectrum of network protocols (Secure Shell - SSH, Transport Layer Security - TLS, etc.);iii) the current state of PQC implementation in key scientific applications (e.g., OpenSSH or SciTokens);iv) the challenges of being quantum-resistant;and v) discussion of potential novel attacks. This is the first large-scale measurement of PQC adoption at national-scale supercomputing centers and FABRIC testbeds. Our results show that only OpenSSH and Google Chrome have successfully implemented PQC and achieved an initial adoption rate of 0.029% (6,044 out of 20,556,816) for OpenSSH connections at NCSA coming from major Internet Service Providers or Autonomous Systems (ASes) such as OARNET, GTT, Google FiberWebpass (U.S.) and Uppsala Lans Landsting (Sweden), with an overall increasing adoption rate year-over-year for 2023-2024. Our analyses identify pathways to migrate current applications to be quantum-resistant.

关键词： adoption rate algorithmic complexity cryptography cyberinfrastructure distributed encrypted data FABRIC Google Chrome migration NCSA networking NIST novel attacks OpenSSH performance Phuong Phuong Cao post-quantum cryptography PQC PQC network instrument quantum computing quantum-resistant quantum-resistant applications scientific applications SSH systems testbed TLS

来源：评论

学校读者我要写书评

暂无评论

A new model and algorithms in firefighting theory

引用

DISCRETE APPLIED MATHEMATICS 2022年 319卷 296-309页

作者： Klein, Rolf Kuebel, David Langetepe, Elmar Sack, Joerg-Ruediger Schwarzwald, Barbara Univ Bonn Dept Comp Sci D-53115 Bonn Germany Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

Continuous and discrete models as well as algorithms Bressan (2007) and Finbow and MacGillivray (2009) for firefighting problems are well-studied in Theoretical Computer Science. We introduce a new, discrete, and more general framework based on a graph to study firefighting problems in various terrains. In the context of this model, we present two different firefighting problems called village protection problems, where the goal to protect a specific set of locations and provide efficient polynomial time algorithms for their solutions. We also discuss extensions of the model. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Combinatorial algorithms algorithmic complexity Discrete geometry Firefighting Frontal propagation Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Multithreading approach for white blood cell segmentation implementation

Multithreading approach for white blood cell segmentation im...

引用

Conference on Real-Time Processing of Image, Depth, and Video Information

作者： Garcia-Salgado, Beatriz P. Ponomaryov, Volodymyr, I Diaz-Resendiz, Jose Luis Mora-Martinez, Yeredith G. Almaraz-Damian, Jose A. Reyes-Reyes, Rogelio Sadovnychiy, Sergiy Inst Politecn Nacl ESIME Culhuacan Mexico City DF Mexico Inst Mexicano Petr Mexico City DF Mexico

ISBN: (纸本)9781510673199;9781510673182

Childhood leukaemia demands meticulous blood cell analysis for diagnosis, focusing on morphological irregularities like asymmetry and abnormal cell counts. Traditional manual diagnosis via microscopic blood smear images suffers from limitations: reduced reliability, time intensiveness, and observer variability. Automated methods using Computer-Aided Diagnostic (CAD) systems address these challenges. Integrating real-time image preprocessing and segmentation ensures swift operation, reducing the CAD system's processing time and enhancing its overall effectiveness, enabling timely medical intervention and better patient outcomes. This study aims to simplify the overall algorithmic complexity of other state-of-the-art techniques using preprocessing steps, including bilateral filtering and Contrast-Limited Adaptive Histogram Equalization (CLAHE), alongside the segmentation stage involving morphological operations and the watershed algorithm. Therefore, an edge-based approach is proposed to enhance the segmentation mask as these operations aggregate time complexity. This work also describes a parallel implementation utilizing OpenMP and CUDA of the proposed method, evaluating its performance using Intersection over Union (IoU) and F1-score metrics along with computing time and algorithmic complexity. Furthermore, computing time is compared using two x86-64 and two ARM architectures, each with a different number of available CPU cores, to evaluate the behaviour of the proposed approach in different conditions. The study highlights the benefits of parallel processing in enhancing the efficiency and accuracy of White Blood Cell (WBC) Segmentation. It reports that the proposed approach has an average IoU of 0.9439 and an F1-score of 0.9697 with an image processing rate higher than 60 images per second.

关键词： White Blood Cell Segmentation Computer-Aided Diagnostic Systems Parallel Processing algorithmic complexity Real-time Segmentation

来源：评论

学校读者我要写书评

暂无评论

Optimization of the scalar complexity of Chudnovsky² multiplication algorithms in finite fields

引用

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES 2021年第4期13卷 495-517页

作者： Ballet, Stephane Bonnecaze, Alexis Dang, Thanh-Hung Aix Marseille Univ CNRS Cent Marseille I2M Marseille France

We propose several constructions for the original multiplication algorithm of D.V. and G.V. Chudnovsky in order to improve its scalar complexity. We highlight the set of generic strategies who underlay the optimization of the scalar complexity, according to parameterizable criteria. As an example, we apply this analysis to the construction of type elliptic Chudnovsky(2) multiplication algorithms for small extensions. As a case study, we significantly improve the Baum-Shokrollahi construction for multiplication in F-256/F-4.

关键词： Finite field Algebraic function field algorithmic complexity

来源：评论

学校读者我要写书评

暂无评论

Eigenvalue Methods for Sparse Tropical Polynomial Systems 8th

Eigenvalue Methods for Sparse Tropical Polynomial Systems

引用

8th International Conference on Mathematical Software (ICMS)

作者： Akian, Marianne Bereau, Antoine Gaubert, Stephane INRIA F-91120 Palaiseau France Inst Polytech Paris CNRS Ecole Polytech CMAP F-91120 Palaiseau France

ISBN: (纸本)9783031645280;9783031645297

We develop an analogue of eigenvalue methods to construct solutions of systems of tropical polynomial equalities and inequalities. We show that solutions can be obtained by solving parametric mean payoff games, arising to approriate linearizations of the systems using tropical Macaulay matrices. We implemented specific algorithms adapted to the large scale parametric games that arise in this way, and present numerical experiments.

关键词： Tropical geometry Polynomial systems Zero-sum games algorithmic complexity

来源：评论

学校读者我要写书评

暂无评论

A comparative evaluation of measures to assess randomness in human-generated sequences

引用

BEHAVIOR RESEARCH METHODS 2024年第7期56卷 7831-7848页

作者： Angelike, Tim Musch, Jochen Heinrich Heine Univ Dusseldorf Inst Expt Psychol Dept Psychol Assessment & Differential Psychol Univ Str 1 D-40225 Dusseldorf Germany

Whether and how well people can behave randomly is of interest in many areas of psychological research. The ability to generate randomness is often investigated using random number generation (RNG) tasks, in which participants are asked to generate a sequence of numbers that is as random as possible. However, there is no consensus on how best to quantify the randomness of responses in human-generated sequences. Traditionally, psychologists have used measures of randomness that directly assess specific features of human behavior in RNG tasks, such as the tendency to avoid repetition or to systematically generate numbers that have not been generated in the recent choice history, a behavior known as cycling. Other disciplines have proposed measures of randomness that are based on a more rigorous mathematical foundation and are less restricted to specific features of randomness, such as algorithmic complexity. More recently, variants of these measures have been proposed to assess systematic patterns in short sequences. We report the first large-scale integrative study to compare measures of specific aspects of randomness with entropy-derived measures based on information theory and measures based on algorithmic complexity. We compare the ability of the different measures to discriminate between human-generated sequences and truly random sequences based on atmospheric noise, and provide a systematic analysis of how the usefulness of randomness measures is affected by sequence length. We conclude with recommendations that can guide the selection of appropriate measures of randomness in psychological research.

关键词： Randomness Human random number generation algorithmic complexity Entropy

来源：评论

学校读者我要写书评

暂无评论

complexity of Lambek Calculi with Modalities and of Total Derivability in Grammars

引用

ALGEBRA AND LOGIC 2021年第5期60卷 308-326页

作者： Dudakov, S. M. Karlov, B. N. Kuznetsov, S. L. Fofanova, E. M. Tver State Univ Tver Russia Russian Acad Sci Steklov Math Inst Moscow Russia Lomonosov Moscow State Univ Moscow Russia

The Lambek calculus with the unit can be defined as the atomic theory (algebraic logic) of the class of residuated monoids. This calculus, being a theory of a broader class of algebras than Heyting ones, is weaker than intuitionistic logic. Namely, it lacks structural rules: permutation, contraction, and weakening. We consider two extensions of the Lambek calculus with modalities-the exponential, under which all structural rules are permitted, and the relevant modality, under which only permutation and contraction rules are allowed. The Lambek calculus with a relevant modality is used in mathematical linguistics. Both calculi are algorithmically undecidable. We consider their fragments in which the modality is allowed to be applied to just formulas of Horn depth not greater than 1. We prove that these fragments are decidable and belong to the NP class. To show this, in the case of a relevant modality, we introduce a new notion of Script capital R-total derivability in context-free grammars, i.e., existence of a derivation in which each rule is used at least a given number of times. It is stated that the Script capital R-totality problem is NP-hard for context-free grammars. Also we pinpoint algorithmic complexity of Script capital R-total derivability for more general classes of generative grammars.

关键词： Lambek calculus substructural logic exponential relevant modality algorithmic complexity context-free grammars total derivability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：