Увійти

Готові списки джерел за темами / Worst-case complexity analysis / Статті в журналах

Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Worst-case complexity analysis.

Статті в журналах з теми "Worst-case complexity analysis"

Автор: Grafiati

Опубліковано: 10 березня 2023

Оновлено: 19 липня 2025

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Ознайомтеся з топ-50 статей у журналах для дослідження на тему "Worst-case complexity analysis".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Переглядайте статті в журналах для різних дисциплін та оформлюйте правильно вашу бібліографію.

1

Szirmay-Kalos, L., and G. Márton. "Worst-case versus average case complexity of ray-shooting." Computing 61, no. 2 (1998): 103–31. http://dx.doi.org/10.1007/bf02684409.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

2

Kwas, Marek, and Youming Li. "Worst case complexity of multivariate Feynman–Kac path integration." Journal of Complexity 19, no. 6 (2003): 730–43. http://dx.doi.org/10.1016/s0885-064x(03)00048-7.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

3

Jackowski, Tomasz. "Complexity of multilinear problems in the worst case setting." Journal of Complexity 6, no. 4 (1990): 389–408. http://dx.doi.org/10.1016/0885-064x(90)90030-h.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

4

Milanese, M., and A. Vicino. "Information-Based Complexity and Nonparametric Worst-Case System Identification." Journal of Complexity 9, no. 4 (1993): 427–46. http://dx.doi.org/10.1006/jcom.1993.1028.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

5

Plaskota, Leszek. "Worst Case Complexity of Problems with Random Information Noise." Journal of Complexity 12, no. 4 (1996): 416–39. http://dx.doi.org/10.1006/jcom.1996.0026.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

6

Pemmaraju, Sriram V., and Clifford A. Shaffer. "Analysis of the worst case space complexity of a PR quadtree." Information Processing Letters 49, no. 5 (1994): 263–67. http://dx.doi.org/10.1016/0020-0190(94)90065-5.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

7

Li, Youming, and Grzegorz W. Wasilkowski. "Worst Case Complexity of Weighted Approximation and Integration over Rd." Journal of Complexity 18, no. 1 (2002): 330–45. http://dx.doi.org/10.1006/jcom.2001.0632.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

8

Kumar, Pijush Kanti. "Breaking the O(n^2) Barrier: Novel Approaches to Time Complexity Analysis in Quick Sort." International Journal of Computer Science and Mobile Computing 9, no. 11 (2020): 107–17. http://dx.doi.org/10.47760/ijcsmc.2020.v09i11.010.

Повний текст джерела

Анотація:

The most common type of sorting algorithm used is quicksort. As the name suggests it is the one of the most fastest sorting algorithm used since the innovation of sorting. However, this sort has often been criticised for its worst-case time complexity that is O(n^2). Practically the quick sort tends to follow its average case and best-case scenarios most of the time. So practically the quick sort is the most efficient practical sorting algorithm. In this paper we will fine tune this algorithm and remove its worst-case time complexity of O(n^2) and make this the best sorting algorithm both theoretically and practically. Various techniques will be discussed from pivot fixing to randomisation and further using medians of medians.

Стилі APA, Harvard, Vancouver, ISO та ін.

9

Short, Michael. "Bounds on Worst-Case Deadline Failure Probabilities in Controller Area Networks." Journal of Computer Networks and Communications 2016 (2016): 1–12. http://dx.doi.org/10.1155/2016/5196092.

Повний текст джерела

Анотація:

Industrial communication networks like the Controller Area Network (CAN) are often required to operate reliably in harsh environments which expose the communication network to random errors. Probabilistic schedulability analysis can employ rich stochastic error models to capture random error behaviors, but this is most often at the expense of increased analysis complexity. In this paper, an efficient method (of time complexityO(n log n)) to bound the message deadline failure probabilities for an industrial CAN network consisting ofnperiodic/sporadic message transmissions is proposed. The paper develops bounds for Deadline Minus Jitter Monotonic (DMJM) and Earliest Deadline First (EDF) message scheduling techniques. Both random errors and random bursts of errors can be included in the model. Stochastic simulations and a case study considering DMJM and EDF scheduling of an automotive benchmark message set provide validation of the technique and highlight its application.

Стилі APA, Harvard, Vancouver, ISO та ін.

10

Rodriguez Ferrandez, Ivan, Alvaro Jover Alvarez, Matina Maria Trompouki, Leonidas Kosmidis, and Francisco J. Cazorla. "Worst Case Execution Time and Power Estimation of Multicore and GPU Software: A Pedestrian Detection Use Case." ACM SIGAda Ada Letters 43, no. 1 (2023): 111–17. http://dx.doi.org/10.1145/3631483.3631502.

Повний текст джерела

Анотація:

Worst Case Execution Time estimation of software running on parallel platforms is a challenging task, due to resource interference of other tasks and the complexity of the underlying CPU and GPU hardware architectures. Similarly, the increased complexity of the hardware, challenges the estimation of worst case power consumption. In this paper, we employ Measurement Based Probabilistic Timing Analysis (MBPTA), which is capable of managing complex architectures such as multicores. We enable its use by software randomisation, which we show for the first time that is also possible on GPUs. We demonstrate our method on a pedestrian detection use case on an embedded multicore and GPU platform for the automotive domain, the NVIDIA Xavier. Moreover, we extend our measurement based probabilistic method in order to predict the worst case power consumption of the software on the same platform.

Стилі APA, Harvard, Vancouver, ISO та ін.

11

De Haan, Ronald, Anna Roubickova, and Stefan Szeider. "Parameterized Complexity Results for Plan Reuse." Proceedings of the AAAI Conference on Artificial Intelligence 27, no. 1 (2013): 224–31. http://dx.doi.org/10.1609/aaai.v27i1.8655.

Повний текст джерела

Анотація:

Planning is a notoriously difficult computational problem of high worst-case complexity. Researchers have been investing significant efforts to develop heuristics or restrictions to make planning practically feasible. Case-based planning is a heuristic approach where one tries to reuse previous experience when solving similar problems in order to avoid some of the planning effort. Plan reuse may offer an interesting alternative to plan generation in some settings. We provide theoretical results that identify situations in which plan reuse is provably tractable. We perform our analysis in the framework of parameterized complexity, which supports a rigorous worst-case complexity analysis that takes structural properties of the input into account in terms of parameters. A central notion of parameterized complexity is fixed-parameter tractability which extends the classical notion of polynomial-time tractability by utilizing the effect of parameters. We draw a detailed map of the parameterized complexity landscape of several variants of problems that arise in the context of case-based planning. In particular, we consider the problem of reusing an existing plan, imposing various restrictions in terms of parameters, such as the number of steps that can be added to the existing plan to turn it into a solution of the planning instance at hand.

Стилі APA, Harvard, Vancouver, ISO та ін.

12

Dai, Qiangqiang, Rong-Hua Li, Donghang Cui, Meihao Liao, Yu-Xuan Qiu, and Guoren Wang. "Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee." Proceedings of the ACM on Management of Data 2, no. 3 (2024): 1–26. http://dx.doi.org/10.1145/3654938.

Повний текст джерела

Анотація:

A k-biplex is an induced subgraph of a bipartite graph which requires every vertex on the one side disconnecting at most k vertices on the other side. Enumerating all maximal k-biplexes in a bipartite graph is a fundamental operator in bipartite graph analysis and finds applications in various domains, including community detection, online recommendation, and fraud detection in finance networks. The state-of-the-art solutions for maximal k-biplex enumeration suffer from efficiency issues as k increases (k ≥ 2), with the time complexity of O(m 2 n ), where n (m) denotes the number of vertices (edges) in the bipartite graph. To address this issue, we propose two theoretically and practically efficient enumeration algorithms based on novel branching techniques. Specifically, we first devise a new branching rule as a fundamental component. Building upon this, we then develop a novel branch-and-bound enumeration algorithm to efficiently enumerate maximal k-biplexes. We prove that our algorithm achieves a worst-case time complexity of O(mα k n ), where α k < 2, thus significantly improving the time complexity compared to previous algorithms. To enhance the performance, we further propose an improved enumeration algorithm based on a novel pivot-based branching rule. Theoretical analysis reveals that our improved algorithm has a time complexity of O(mβ k n ), where β k is strictly less than α k . In addition, we also present several non-trivial optimization techniques, including graph reduction, upper-bounds based pruning, and ordering-based optimization, to further improve the efficiency of our algorithms. Finally, we conduct extensive experiments on 6 large real-world bipartite graphs to evaluate the efficiency and scalability of the proposed solutions. The results demonstrate that our improved algorithm achieves up to 5 orders of magnitude faster than the state-of-the-art solutions.

Стилі APA, Harvard, Vancouver, ISO та ін.

13

Kon, Mark, and Leszek Plaskota. "Complexity of Neural Network Approximation with Limited Information: A Worst Case Approach." Journal of Complexity 17, no. 2 (2001): 345–65. http://dx.doi.org/10.1006/jcom.2001.0575.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

14

Vakhania, Nodari. "Probabilistic quality estimations for combinatorial optimization problems." Georgian Mathematical Journal 25, no. 1 (2018): 123–34. http://dx.doi.org/10.1515/gmj-2017-0041.

Повний текст джерела

Анотація:

AbstractThe computational complexity of an algorithm is traditionally measured for the worst and the average case. The worst-case estimation guarantees a certain worst-case behavior of a given algorithm, although it might be rough, since in “most instances” the algorithm may have a significantly better performance. The probabilistic average-case analysis claims to derive an average performance of an algorithm, say, for an “average instance” of the problem in question. That instance may be far away from the average of the problem instances arising in a given real-life application, and so the average case analysis would also provide a non-realistic estimation. We suggest that, in general, a wider use of probabilistic models for a more accurate estimation of the algorithm efficiency could be possible. For instance, the quality of the solutions delivered by an approximation algorithm may also be estimated in the “average” probabilistic case. Such an approach would deal with the estimation of the quality of the solutions delivered by the algorithm for the most common (for a given application) problem instances. As we illustrate, the probabilistic modeling can also be used to derive an accurate time complexity performance measure, distinct from the traditional probabilistic average-case time complexity measure. Such an approach could, in particular, be useful when the traditional average-case estimation is still rough or is not possible at all.

Стилі APA, Harvard, Vancouver, ISO та ін.

15

Chan, Tsz Nam, Leong Hou U, Yun Peng, Byron Choi, and Jianliang Xu. "Fast network k-function-based spatial analysis." Proceedings of the VLDB Endowment 15, no. 11 (2022): 2853–66. http://dx.doi.org/10.14778/3551793.3551836.

Повний текст джерела

Анотація:

Network K -function has been the de facto operation for analyzing point patterns in spatial networks, which is widely used in many communities, including geography, ecology, transportation science, social science, and criminology. To analyze a location dataset, domain experts need to generate a network K -function plot that involves computing multiple network K -functions. However, network K -function is a computationally expensive operation that is not feasible to support large-scale datasets, let alone to generate a network K -function plot. To handle this issue, we develop two efficient algorithms, namely count augmentation (CA) and neighbor sharing (NS), which can reduce the worst-case time complexity for computing network K -functions. In addition, we incorporate the advanced shortest path sharing (ASPS) approach into these two methods to further lower the worst-case time complexity for generating network K -function plots. Experiment results on four large-scale location datasets (up to 7.33 million data points) show that our methods can achieve up to 165.85x speedup compared with the state-of-the-art methods.

Стилі APA, Harvard, Vancouver, ISO та ін.

16

Matsuo, Hirofumi. "Cyclic sequencing problems in the two-machine permutation flow shop: Complexity, worst-case, and average-case analysis." Naval Research Logistics 37, no. 5 (1990): 679–94. http://dx.doi.org/10.1002/1520-6750(199010)37:5<679::aid-nav3220370507>3.0.co;2-q.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

17

Kacewicz, Bolesław. "Asymptotically tight worst case complexity bounds for initial-value problems with nonadaptive information." Journal of Complexity 47 (August 2018): 86–96. http://dx.doi.org/10.1016/j.jco.2018.02.002.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

18

ASCHIERI, FEDERICO. "GAME SEMANTICS AND THE GEOMETRY OF BACKTRACKING: A NEW COMPLEXITY ANALYSIS OF INTERACTION." Journal of Symbolic Logic 82, no. 2 (2017): 672–708. http://dx.doi.org/10.1017/jsl.2016.48.

Повний текст джерела

Анотація:

AbstractWe present abstract complexity results about Coquand and Hyland–Ong game semantics, that will lead to new bounds on the length of first-order cut-elimination, normalization, interaction between expansion trees and any other dialogical process game semantics can model and apply to. In particular, we provide a novel method to bound the length of interactions between visible strategies and to measure precisely the tower of exponentials defining the worst-case complexity. Our study improves the old estimates on average by several exponentials.

Стилі APA, Harvard, Vancouver, ISO та ін.

19

Gordon, Ofir, Yuval Filmus, and Oren Salzman. "Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds." Proceedings of the International Symposium on Combinatorial Search 12, no. 1 (2021): 64–72. http://dx.doi.org/10.1609/socs.v12i1.18552.

Повний текст джерела

Анотація:

The problem of Multi-Agent Path Finding (MAPF) calls for finding a set of conflict-free paths for a fleet of agents operating in a given environment. Arguably, the state-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS). In this work we revisit the complexity analysis of CBS to provide tighter bounds on the algorithm's run-time in the worst-case. Our analysis paves the way to better pinpoint the parameters that govern (in the worst case) the algorithm's computational complexity. Our analysis is based on two complementary approaches: In the first approach we bound the run-time using the size of a Multi-valued Decision Diagram (MDD)--a layered graph which compactly contains all possible single-agent paths between two given vertices for a specific path length. In the second approach we express the running time by a novel recurrence relation which bounds the algorithm's complexity. We use generating functions-based analysis in order to tightly bound the recurrence. Using these technique we provide several new upper-bounds on CBS's complexity. The results allow us to improve the existing bound on the running time of CBS for many cases. For example, on a set of common benchmarks we improve the upper-bound by a factor of at least 2 to the power of 10,000,000.

Стилі APA, Harvard, Vancouver, ISO та ін.

20

Cade, Chris, Marten Folkertsma, Ido Niesen, and Jordi Weggemans. "Quantifying Grover speed-ups beyond asymptotic analysis." Quantum 7 (October 10, 2023): 1133. http://dx.doi.org/10.22331/q-2023-10-10-1133.

Повний текст джерела

Анотація:

Run-times of quantum algorithms are often studied via an asymptotic, worst-case analysis. Whilst useful, such a comparison can often fall short: it is not uncommon for algorithms with a large worst-case run-time to end up performing well on instances of practical interest. To remedy this it is necessary to resort to run-time analyses of a more empirical nature, which for sufficiently small input sizes can be performed on a quantum device or a simulation thereof. For larger input sizes, alternative approaches are required.In this paper we consider an approach that combines classical emulation with detailed complexity bounds that include all constants. We simulate quantum algorithms by running classical versions of the sub-routines, whilst simultaneously collecting information about what the run-time of the quantum routine would have been if it were run instead. To do this accurately and efficiently for very large input sizes, we describe an estimation procedure and prove that it obtains upper bounds on the true expected complexity of the quantum algorithms.We apply our method to some simple quantum speedups of classical heuristic algorithms for solving the well-studied MAX-k-SAT optimization problem. This requires rigorous bounds (including all constants) on the expected- and worst-case complexities of two important quantum sub-routines: Grover search with an unknown number of marked items, and quantum maximum-finding. These improve upon existing results and might be of broader interest.Amongst other results, we found that the classical heuristic algorithms we studied did not offer significant quantum speedups despite the existence of a theoretical per-step speedup. This suggests that an empirical analysis such as the one we implement in this paper already yields insights beyond those that can be seen by an asymptotic analysis alone.

Стилі APA, Harvard, Vancouver, ISO та ін.

21

HARRINGTON, PAUL, COLM Ó. DÚNLAING, and CHEE K. YAP. "OPTIMAL VORONOI DIAGRAM CONSTRUCTION WITH n CONVEX SITES IN THREE DIMENSIONS." International Journal of Computational Geometry & Applications 17, no. 06 (2007): 555–93. http://dx.doi.org/10.1142/s0218195907002483.

Повний текст джерела

Анотація:

This paper presents a worst-case optimal algorithm for constructing the Voronoi diagram for n disjoint convex and rounded semi-algebraic sites in 3 dimensions. Rather than extending optimal 2-dimensional methods,32,16,20,2 we base our method on a suboptimal 2-dimensional algorithm, outlined by Lee and Drysdale and modified by Sharir25,30 for computing the diagram of circular sites. For complexity considerations, we assume the sites have bounded complexity, i.e., the algebraic degree is bounded as is the number of algebraic patches making up the site. For the sake of simplicity we assume that the sites are what we call rounded. This assumption simplifies the analysis, though it is probably unnecessary. Our algorithm runs in time O(C(n)) where C(n) is the worst-case complexity of an n-site diagram. For spherical sites C(n) is θ(n2), but sharp estimates do not seem to be available for other classes of site.

Стилі APA, Harvard, Vancouver, ISO та ін.

22

Han, Ai Li. "Complexity Research on B Algorithm." Applied Mechanics and Materials 20-23 (January 2010): 173–77. http://dx.doi.org/10.4028/www.scientific.net/amm.20-23.173.

Повний текст джерела

Анотація:

The time complexity of B algorithm, one of the intelligent search algorithms, is discussed. By anatomizing some instances, it is pointed out that the cost of calculating the value of heuristic function should be included in the range of time complexity analysis for B algorithm. And then, an algorithm of calculating the value of heuristic function is presented. By analyzing the cost of calculating the value of heuristic function, it is pointed out that the number of recursions in B algorithm is O(n!) in the worst case. Therefore, the time complexity of B algorithm is exponential instead of O(n2).

Стилі APA, Harvard, Vancouver, ISO та ін.

23

Journal, IJSREM. "Advanced In-Place Merge Sort Approach for Enhanced Sorting Performance." INTERANTIONAL JOURNAL OF SCIENTIFIC RESEARCH IN ENGINEERING AND MANAGEMENT 08, no. 008 (2024): 1–5. http://dx.doi.org/10.55041/ijsrem37088.

Повний текст джерела

Анотація:

This paper introduces a new sorting algorithm designed to sort array elements directly within the array itself. The algorithm features a best-case time complexity of O(n) and an average and worst-case time complexity of O (n log n). It achieves this performance through a method that combines recursive breakdown with in-place merging techniques. We compare this new approach with existing popular sorting algorithms to assess its relative effectiveness. The paper concludes with insights into the algorithm's strengths and limitations, and proposes potential areas for further development and refinement. Keywords - Complexity Analysis, In-Place Sorting, Recursive Breakdown

Стилі APA, Harvard, Vancouver, ISO та ін.

24

Procaccia, A. D., and J. S. Rosenschein. "Junta Distributions and the Average-Case Complexity of Manipulating Elections." Journal of Artificial Intelligence Research 28 (February 28, 2007): 157–81. http://dx.doi.org/10.1613/jair.2148.

Повний текст джерела

Анотація:

Encouraging voters to truthfully reveal their preferences in an election has long been an important issue. Recently, computational complexity has been suggested as a means of precluding strategic behavior. Previous studies have shown that some voting protocols are hard to manipulate, but used NP-hardness as the complexity measure. Such a worst-case analysis may be an insufficient guarantee of resistance to manipulation. Indeed, we demonstrate that NP-hard manipulations may be tractable in the average case. For this purpose, we augment the existing theory of average-case complexity with some new concepts. In particular, we consider elections distributed with respect to junta distributions, which concentrate on hard instances. We use our techniques to prove that scoring protocols are susceptible to manipulation by coalitions, when the number of candidates is constant.

Стилі APA, Harvard, Vancouver, ISO та ін.

25

Kuhlmann, Marco, Giorgio Satta, and Peter Jonsson. "On the Complexity of CCG Parsing." Computational Linguistics 44, no. 3 (2018): 447–82. http://dx.doi.org/10.1162/coli_a_00324.

Повний текст джерела

Анотація:

We study the parsing complexity of Combinatory Categorial Grammar (CCG) in the formalism of Vijay-Shanker and Weir ( 1994 ). As our main result, we prove that any parsing algorithm for this formalism will take in the worst case exponential time when the size of the grammar, and not only the length of the input sentence, is included in the analysis. This sets the formalism of Vijay-Shanker and Weir ( 1994 ) apart from weakly equivalent formalisms such as Tree Adjoining Grammar, for which parsing can be performed in time polynomial in the combined size of grammar and input sentence. Our results contribute to a refined understanding of the class of mildly context-sensitive grammars, and inform the search for new, mildly context-sensitive versions of CCG.

Стилі APA, Harvard, Vancouver, ISO та ін.

26

Goldman, C. V., and S. Zilberstein. "Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis." Journal of Artificial Intelligence Research 22 (November 1, 2004): 143–74. http://dx.doi.org/10.1613/jair.1427.

Повний текст джерела

Анотація:

Decentralized control of cooperative systems captures the operation of a group of decision makers that share a single global objective. The difficulty in solving optimally such problems arises when the agents lack full observability of the global state of the system when they operate. The general problem has been shown to be NEXP-complete. In this paper, we identify classes of decentralized control problems whose complexity ranges between NEXP and P. In particular, we study problems characterized by independent transitions, independent observations, and goal-oriented objective functions. Two algorithms are shown to solve optimally useful classes of goal-oriented decentralized processes in polynomial time. This paper also studies information sharing among the decision-makers, which can improve their performance. We distinguish between three ways in which agents can exchange information: indirect communication, direct communication and sharing state features that are not controlled by the agents. Our analysis shows that for every class of problems we consider, introducing direct or indirect communication does not change the worst-case complexity. The results provide a better understanding of the complexity of decentralized control problems that arise in practice and facilitate the development of planning algorithms for these problems.

Стилі APA, Harvard, Vancouver, ISO та ін.

27

Lee, Ching-pei, and Stephen J. Wright. "Random permutations fix a worst case for cyclic coordinate descent." IMA Journal of Numerical Analysis 39, no. 3 (2018): 1246–75. http://dx.doi.org/10.1093/imanum/dry040.

Повний текст джерела

Анотація:

Abstract Variants of the coordinate descent approach for minimizing a nonlinear function are distinguished in part by the order in which coordinates are considered for relaxation. Three common orderings are cyclic (CCD), in which we cycle through the components of $x$ in order; randomized (RCD), in which the component to update is selected randomly and independently at each iteration; and random-permutations cyclic (RPCD), which differs from CCD only in that a random permutation is applied to the variables at the start of each cycle. Known convergence guarantees are weaker for CCD and RPCD than for RCD, though in most practical cases, computational performance is similar among all these variants. There is a certain type of quadratic function for which CCD is significantly slower than for RCD; a recent paper by Sun & Ye (2016, Worst-case complexity of cyclic coordinate descent: $O(n^2)$ gap with randomized version. Technical Report. Stanford, CA: Department of Management Science and Engineering, Stanford University. arXiv:1604.07130) has explored the poor behavior of CCD on functions of this type. The RPCD approach performs well on these functions, even better than RCD in a certain regime. This paper explains the good behavior of RPCD with a tight analysis.

Стилі APA, Harvard, Vancouver, ISO та ін.

28

Yan, Huichao, and Jia Chen. "Tractability of Approximation of Functions Defined over Weighted Hilbert Spaces." Axioms 13, no. 2 (2024): 108. http://dx.doi.org/10.3390/axioms13020108.

Повний текст джерела

Анотація:

We investigate L2-approximation problems in the worst case setting in the weighted Hilbert spaces H(KRd,α,γ) with weights Rd,α,γ under parameters 1≥γ1≥γ2≥⋯≥0 and 1<α1≤α2≤⋯. Several interesting weighted Hilbert spaces H(KRd,α,γ) appear in this paper. We consider the worst case error of algorithms that use finitely many arbitrary continuous linear functionals. We discuss tractability of L2-approximation problems for the involved Hilbert spaces, which describes how the information complexity depends on d and ε−1. As a consequence we study the strongly polynomial tractability (SPT), polynomial tractability (PT), weak tractability (WT), and (t1,t2)-weak tractability ((t1,t2)-WT) for all t1>1 and t2>0 in terms of the introduced weights under the absolute error criterion or the normalized error criterion.

Стилі APA, Harvard, Vancouver, ISO та ін.

29

Della Croce, Federico, and Vangelis Th Paschos. "Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems." Operational Research 8, no. 3 (2008): 235–56. http://dx.doi.org/10.1007/s12351-008-0020-8.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

30

Hu, Xiao, and Qichen Wang. "Towards Update-Dependent Analysis of Query Maintenance." Proceedings of the ACM on Management of Data 3, no. 2 (2025): 1–25. https://doi.org/10.1145/3725254.

Повний текст джерела

Анотація:

This paper studies the hardness of maintaining self-join-free conjunctive queries over a dynamic database, where tuples can be inserted or deleted. The worst-case complexity of this problem under arbitrary updates has been well understood. It is known that most practical queries require Ω(√|D|) maintenance time for each update to ensure O(1)-delay enumeration, barring a very restricted class of queries (known as "q-hierarchical" queries). Nonetheless, most real-world update sequences are not arbitrary, far away from the worst-case scenario; instead, they are so "nice" that queries can greatly benefit from their inherent structure in query maintenance. In this paper, we aim to understand the hardness of query maintenance under different update sequences, in particular, the insertion-only (or deletion-only), first-in-first-out (FIFO), arbitrarily worse sequences, as well as their "mixed" sequences. We first provide a comprehensive characterization of queries that can be maintained in O(1) time for O(1)-delay enumeration over FIFO sequences. Then, we address mixed sequences, which may exhibit insertion-only or FIFO patterns on subqueries but lack a specific pattern in totality, and introduce a structural dichotomy for determining whether the input query can be maintained in O(1) time for O(1)-delay enumeration over mixed sequences.

Стилі APA, Harvard, Vancouver, ISO та ін.

31

Anastasi, G., P. Foglia, and L. Lenzini. "MPEG video traffic on a MetaRing network: complexity reduction of a ‘worst-case’ model for bandwidth allocation analysis." Computer Communications 21, no. 2 (1998): 111–25. http://dx.doi.org/10.1016/s0140-3664(97)00135-7.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

32

Barbay, Jérémy. "Optimal Prefix Free Codes with Partial Sorting." Algorithms 13, no. 1 (2019): 12. http://dx.doi.org/10.3390/a13010012.

Повний текст джерела

Анотація:

We describe an algorithm computing an optimal prefix free code for n unsorted positive weights in time within O ( n ( 1 + lg α ) ) ⊆ O ( n lg n ) , where the alternation α ∈ [ 1 . . n − 1 ] approximates the minimal amount of sorting required by the computation. This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of size n and alternation α . Such results refine the state of the art complexity of Θ ( n lg n ) in the worst case over instances of size n in the same computational model, a landmark in compression and coding since 1952. Beside the new analysis technique, such improvement is obtained by combining a new algorithm, inspired by van Leeuwen’s algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with a relatively minor extension of Karp et al.’s deferred data structure to partially sort a multiset accordingly to the queries performed on it (known since 1988). Preliminary experimental results on text compression by words show α to be polynomially smaller than n, which suggests improvements by at most a constant multiplicative factor in the running time for such applications.

Стилі APA, Harvard, Vancouver, ISO та ін.

33

Xia, Lirong, and Weiqiang Zheng. "The Smoothed Complexity of Computing Kemeny and Slater Rankings." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 6 (2021): 5742–50. http://dx.doi.org/10.1609/aaai.v35i6.16720.

Повний текст джерела

Анотація:

The computational complexity of winner determination under common voting rules is a classical and fundamental topic in the field of computational social choice. Previous work has established the NP-hardness of winner determination under some commonly-studied voting rules, such as the Kemeny rule and the Slater rule. In a recent position paper, Baumeister, Hogrebe, and Rothe (2020) questioned the relevance of the worst-case nature of NP-hardness in social choice and proposed to conduct smoothed complexity analysis (Spielman and Teng 2009) under Blaser and Manthey’s (2015) framework. In this paper, we develop the first smoothed complexity results for winner determination in voting. We prove the smoothed hardness of Kemeny and Slater using the classical smoothed runtime analysis, and prove a parameterized typical-case smoothed easiness result for Kemeny. We also make an attempt of applying Blaser and Manthey’s (2015) smoothed complexity framework in social choice contexts by proving that the framework categorizes an always-exponential-time brute force search algorithm as being smoothed poly-time, under a natural noise model based on the well-studied Mallows model in social choice and statistics. Overall, our results show that smoothed complexity analysis in computational social choice is a challenging and fruitful topic.

Стилі APA, Harvard, Vancouver, ISO та ін.

34

Dai, Jingke, Peng Zhao, Xiao Chen, and Fenggan Zhang. "Analysis and Design of Systematic Rateless Codes in FH/BFSK System with Interference." Mobile Information Systems 2020 (February 10, 2020): 1–8. http://dx.doi.org/10.1155/2020/9049284.

Повний текст джерела

Анотація:

The asymptotic analysis of systematic rateless codes in frequency hopping (FH) systems with interference is first provided using discretized density evolution (DDE) and compared with the traditional fixed-rate scheme. A simplified analysis with Gaussian assumption of initial message is proposed in the worst case of interference, which has much lower complexity and provides a very close result to DDE. Based on this simplified analysis, the linear programming is employed to design rateless codes and the simulation results on partial-band interference channels show that the optimized codes have more powerful antijamming performance than the codes originally designed for conventional systems.

Стилі APA, Harvard, Vancouver, ISO та ін.

35

Touil, Imene, and Wided Chikouche. "Primal-dual interior point methods for Semidefinite programming based on a new type of kernel functions." Filomat 34, no. 12 (2020): 3957–69. http://dx.doi.org/10.2298/fil2012957t.

Повний текст джерела

Анотація:

In this paper, we propose the first hyperbolic-logarithmic kernel function for Semidefinite programming problems. By simple analysis tools, several properties of this kernel function are used to compute the total number of iterations. We show that the worst-case iteration complexity of our algorithm for large-update methods improves the obtained iteration bounds based on hyperbolic [24] as well as classic kernel functions. For small-update methods, we derive the best known iteration bound.

Стилі APA, Harvard, Vancouver, ISO та ін.

36

Khan, Farhan Hai, Tannistha Pal, and Rounik Roy. "Development of a Universal Running Time Predictor using Multivariate Regression." International Journal of Innovative Research in Physics 3, no. 3 (2022): 1–9. http://dx.doi.org/10.15864/ijiip.3301.

Повний текст джерела

Анотація:

Various types of running times exist for analysis of algorithmic efficiency. This research presents a more empirical approach to the problem for the practical measurements of the actual running time of algorithms by considering a plethora of randomized inputs Rn and then fitting a regression curve in n to the algorithm of practical time complexity ν (n). This will also provide us the productivity factor η which will quantify the universal running time with respect to the asymptotic worst-case complexity and evaluate the efficiency of the given algorithm with the help of leading coefficients. This research will also help us compare similar algorithms in a mathematically modelled manner.

Стилі APA, Harvard, Vancouver, ISO та ін.

37

Neunhöffer, Max, and Cheryl E. Praeger. "Computing Minimal Polynomials of Matrices." LMS Journal of Computation and Mathematics 11 (2008): 252–79. http://dx.doi.org/10.1112/s1461157000000590.

Повний текст джерела

Анотація:

AbstractWe present and analyse a Monte-Carlo algorithm to compute the minimal polynomial of ann × nmatrix over a finite field that requiresO(n3) field operations andO(n) random vectors, and is well suited for successful practical implementation. The algorithm, and its complexity analysis, use standard algorithms for polynomial and matrix operations. We compare features of the algorithm with several other algorithms in the literature. In addition we present a deterministic verification procedure which is similarly efficient in most cases but has a worst-case complexity ofO(n4). Finally, we report the results of practical experiments with an implementation of our algorithms in comparison with the current algorithms in the GAP library.

Стилі APA, Harvard, Vancouver, ISO та ін.

38

Selvi, V. "Clustering Analysis of Greedy Heuristic Method in Zero_One Knapsack Problem." International Journal of Emerging Research in Management and Technology 6, no. 7 (2018): 39. http://dx.doi.org/10.23956/ijermt.v6i7.181.

Повний текст джерела

Анотація:

Knapsack problem is a surely understood class of optimization problems, which tries to expand the profit of items in a knapsack without surpassing its capacity, Knapsack can be solved by several algorithms such like Greedy, dynamic programming, Branch & bound etc. The solution to the zero_one knapsack problem (KP) can be viewed as the result of a sequence of decision. Clustering is the process of resolving that type of applications. Different clustering application for grouping elements with equal priority. In this paper we are introducing greedy heuristic algorithm for solving zero_one knapsack problem. We will exhibit a relative investigation of the Greedy, dynamic programming, B&B and Genetic algorithms regarding of the complexity of time requirements, and the required programming efforts and compare the total value for each of them. Greedy and Genetic algorithms can be used to solve the 0-1 Knapsack problem within a reasonable time complexity. The worst-case time complexity (Big-O) of both algorithms is O(N). Using the greedy method, the algorithm can produce high quality clusters while reduce time the best partioning avoid the memory confinement problem during the process.

Стилі APA, Harvard, Vancouver, ISO та ін.

39

Yu, Kaiqiang, Kaixin Wang, Cheng Long, Laks Lakshmanan, and Reynold Cheng. "Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach." Proceedings of the ACM on Management of Data 3, no. 3 (2025): 1–27. https://doi.org/10.1145/3725404.

Повний текст джерела

Анотація:

Given two input graphs, finding the largest subgraph that occurs in both, i.e., finding the maximum common subgraph, is a fundamental operator for evaluating the similarity between two graphs in graph data analysis. Existing works for solving the problem are of either theoretical or practical interest, but not both. Specifically, the algorithms with a theoretical guarantee on the running time are known to be not practically efficient; algorithms following the recently proposed backtracking framework called McSplit, run fast in practice but do not have any theoretical guarantees. In this paper, we propose a new backtracking algorithm called RRSplit, which at once achieves better practical efficiency and provides a non-trivial theoretical guarantee on the worst-case running time. To achieve the former, we develop a series of reductions and upper bounds for reducing redundant computations, i.e., the time for exploring some unpromising branches of exploration that hold no maximum common subgraph. To achieve the latter, we formally prove that RRSplit incurs a worst-case time complexity which matches the best-known complexity for the problem. Finally, we conduct extensive experiments on four benchmark graph collections, and the results demonstrate that our algorithm outperforms the practical state-of-the-art by several orders of magnitude.

Стилі APA, Harvard, Vancouver, ISO та ін.

40

Jiang, Tianzi. "The worst case complexity of the fredholm equation of the second kind with non-periodic free term and noise information." Numerical Functional Analysis and Optimization 19, no. 3-4 (1998): 329–43. http://dx.doi.org/10.1080/01630569808816831.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

41

Song, Xin, Jingguo Ren, and Qiuming Li. "Doubly Constrained Robust Blind Beamforming Algorithm." Journal of Applied Mathematics 2013 (2013): 1–8. http://dx.doi.org/10.1155/2013/245609.

Повний текст джерела

Анотація:

We propose doubly constrained robust least-squares constant modulus algorithm (LSCMA) to solve the problem of signal steering vector mismatches via the Bayesian method and worst-case performance optimization, which is based on the mismatches between the actual and presumed steering vectors. The weight vector is iteratively updated with penalty for the worst-case signal steering vector by the partial Taylor-series expansion and Lagrange multiplier method, in which the Lagrange multipliers can be optimally derived and incorporated at each step. A theoretical analysis for our proposed algorithm in terms of complexity cost, convergence performance, and SINR performance is presented in this paper. In contrast to the linearly constrained LSCMA, the proposed algorithm provides better robustness against the signal steering vector mismatches, yields higher signal captive performance, improves greater array output SINR, and has a lower computational cost. The simulation results confirm the superiority of the proposed algorithm on beampattern control and output SINR enhancement.

Стилі APA, Harvard, Vancouver, ISO та ін.

42

Zhao, Lulu, Guang Liang, and Huijie Liu. "An Improved Robust Beamforming Design for Cognitive Multiantenna Relay Networks." Mobile Information Systems 2017 (2017): 1–11. http://dx.doi.org/10.1155/2017/2719543.

Повний текст джерела

Анотація:

This paper investigates the robust relay beamforming design for the multiantenna nonregenerative cognitive relay networks (CRNs). Firstly, it is proved that the optimal beamforming matrix could be simplified as the product of a variable vector and the conjugate transposition of a known channel response vector. Then, by exploiting the optimal beamforming matrix with simplified structure, an improved robust beamforming design is proposed. Analysis and simulation results show that, compared with the existing suboptimal scheme, the proposed method can achieve higher worst-case channel capacity with lower computational complexity.

Стилі APA, Harvard, Vancouver, ISO та ін.

43

Liu, Yang, Hejiao Huang, Kaiqiang Yu, Shengxin Liu, and Cheng Long. "Efficient Maximum s -Bundle Search via Local Vertex Connectivity." Proceedings of the ACM on Management of Data 3, no. 1 (2025): 1–27. https://doi.org/10.1145/3709687.

Повний текст джерела

Анотація:

The s -bundle, as a cohesive subgraph model which relaxes the clique, remains connected whenever fewer than n-s vertices are removed, where n is the number of vertices inside. Finding the largest s -bundle is a fundamental problem and has diverse applications in various fields such as social network analysis, graph visualization, and bioinformatics. Existing studies for solving the problem follow the same branch-and-bound framework and improve the efficiency by developing pruning techniques. As a result, all share the same worst-case time complexity of O* (2 n ), where O* suppresses the polynomial factors. In this paper, we propose a new branch-and-bound algorithm, called SymBD, which achieves improved theoretical guarantees and practical performance. It adopts the existing Symmetric-BK branching strategy whose performance highly depends on the ordering of vertices. We explore various vertex orderings for improving the performance. In particular, we propose two novel vertex orderings based on the local vertex connectivity. With the proposed vertex orderings, SymBD improves the worst-case time complexity to O* (λ n s ) where λ s is strictly less than 2. To further boost the practical efficiency, we introduce a heuristic algorithm for computing a large initial solution and a divide-and-conquer strategy. Extensive experiments on 664 graphs demonstrate that our algorithm is up to five orders of magnitude faster than existing solutions.

Стилі APA, Harvard, Vancouver, ISO та ін.

44

WANG, BIING-FENG. "A BETTER ANALYSIS OF BEN-ASHER’S ALGORITHM FOR THE CONDITIONAL CARTESIAN PRODUCT PROBLEM." Parallel Processing Letters 06, no. 03 (1996): 331–44. http://dx.doi.org/10.1142/s0129626496000327.

Повний текст джерела

Анотація:

In [2], a new problem called conditional cartesian product problem was introduced. The problem has a trivial time lower bound [Formula: see text], where A and B are two groups of N elements and CA,B is a subset of the cartesian product A×B satisfying some unknown condition C. Ben-Asher proposed an efficient algorithm for the problem and showed that the proposed algorithm can be performed in [Formula: see text] time [2]. As compared with the trivial time lower bound, the algorithm is not optimal. In this paper, with a better analysis, we show that the worst-case time complexity of Ben-Asher’s algorithm is [Formula: see text], which is much better than [Formula: see text]. Consequently, it can be concluded that for case the rate of growth of |CA,B| is not smaller than [Formula: see text] is a tight lower bound and Ben-Asher’s algorithm is indeed optimal.

Стилі APA, Harvard, Vancouver, ISO та ін.

45

Behnke, Gregor, and Marcel Steinmetz. "On the Computational Complexity of Stackelberg Planning and Meta-Operator Verification." Proceedings of the International Conference on Automated Planning and Scheduling 34 (May 30, 2024): 20–24. http://dx.doi.org/10.1609/icaps.v34i1.31456.

Повний текст джерела

Анотація:

Stackelberg planning is a recently introduced single-turn two-player adversarial planning model, where two players are acting in a joint classical planning task, the objective of the first player being hampering the second player from achieving its goal. This places the Stackelberg planning problem somewhere between classical planning and general combinatorial two-player games. But, where exactly? All investigations of Stackelberg planning so far focused on practical aspects. We close this gap by conducting the first theoretical complexity analysis of Stackelberg planning. We show that in general Stackelberg planning is actually no harder than classical planning. Under a polynomial plan-length restriction, however, Stackelberg planning is a level higher up in the polynomial complexity hierarchy, suggesting that compilations into classical planning come with a worst-case exponential plan-length increase. In attempts to identify tractable fragments, we further study its complexity under various planning task restrictions, showing that Stackelberg planning remains intractable where classical planning is not. We finally inspect the complexity of meta-operator verification, a problem that has been recently connected to Stackelberg planning.

Стилі APA, Harvard, Vancouver, ISO та ін.

46

Meghdouri, Fares, Félix Iglesias Vázquez, and Tanja Zseby. "Modeling data with observers." Intelligent Data Analysis 26, no. 3 (2022): 785–803. http://dx.doi.org/10.3233/ida-215741.

Повний текст джерела

Анотація:

Compact data models have become relevant due to the massive, ever-increasing generation of data. We propose Observers-based Data Modeling (ODM), a lightweight algorithm to extract low density data models (aka coresets) that are suitable for both static and stream data analysis. ODM coresets keep data internal structures while alleviating computational costs of machine learning during evaluation phases accounting for a O(n log n) worst-case complexity. We compare ODM with previous proposals in classification, clustering, and outlier detection. Results show the preponderance of ODM for obtaining the best trade-off in accuracy, versatility, and speed.

Стилі APA, Harvard, Vancouver, ISO та ін.

47

Meghdouri, Fares, Félix Iglesias Vázquez, and Tanja Zseby. "Modeling data with observers." Intelligent Data Analysis 26, no. 3 (2022): 785–803. http://dx.doi.org/10.3233/ida-215741.

Повний текст джерела

Анотація:

Compact data models have become relevant due to the massive, ever-increasing generation of data. We propose Observers-based Data Modeling (ODM), a lightweight algorithm to extract low density data models (aka coresets) that are suitable for both static and stream data analysis. ODM coresets keep data internal structures while alleviating computational costs of machine learning during evaluation phases accounting for a O(n log n) worst-case complexity. We compare ODM with previous proposals in classification, clustering, and outlier detection. Results show the preponderance of ODM for obtaining the best trade-off in accuracy, versatility, and speed.

Стилі APA, Harvard, Vancouver, ISO та ін.

48

Xu, Zhang Yan, Wei Zhang, and Yan Ying Fan. "Attribute Reduction Algorithm of Incomplete Dicision Table Based on Conditional Entropy." Applied Mechanics and Materials 380-384 (August 2013): 1505–9. http://dx.doi.org/10.4028/www.scientific.net/amm.380-384.1505.

Повний текст джерела

Анотація:

The search of the attribute reduction algorithm of rough set in incomplete decision table is a research hot spot. Though analysis of the advantages and disadvantages of the existing attribute reduction algorithms,we put forward a definition of relative discernibility matrix base on the positive area. Then we compute the tolerance class with the the idea of cardinal number sorting method, giving a quick heuristic algorithm of attribute reduction with theconditional entropy and relative discernibility matrix, which of the time complexity is in the worst case. The test result shows that the algorithm can obtain an attribute reduction efficiently.

Стилі APA, Harvard, Vancouver, ISO та ін.

49

García Ojeda, Juan Carlos. "A Look at Algorithm BEPtoPNST." Revista Ingenierías Universidad de Medellín 20, no. 39 (2020): 115–28. http://dx.doi.org/10.22395/rium.v20n39a7.

Повний текст джерела

Анотація:

This work analyzes the computational complexity of algorithm BEPtoPNST which transforms a building-evacuation problem (BEP) into a time-ex-panded, process-network synthesis (PNST) problem. The solution of the latter is achieved by resorting to the P-graph method which exploits the combinatorial nature of a BEP. Unlike other approaches, the P-graph method provides not only the optimal solution (best evacuation route as a function of egress time), but also the best n sub-optimal solutions. For the complexity analysis, a generic processor, and a Random-access machine (RAM) model were deployed as well as a mathematical model to calculate the number and cost of the operations performed. It was observed that algorithm BEPtoPNST exhibits an asymptotic complexity of order O ( T | A | (| N | –k)). When solving a BEP, however, the total complexity grows exponentially with order O (T | A | (| N | –k)) + O (2h)) in the worst case; where h represents the total number of operating units specified in the corresponding PNST problem. Nevertheless, the computational comple-xity can be reduced significantly when the P-graph method is deployed.

Стилі APA, Harvard, Vancouver, ISO та ін.

50

Liu, Fangyao, Yayu Peng, Zhengxin Chen, and Yong Shi. "Modeling of Characteristics on Artificial Intelligence IQ Test: a Fuzzy Cognitive Map-Based Dynamic Scenario Analysis." International Journal of Computers Communications & Control 14, no. 6 (2019): 653–69. http://dx.doi.org/10.15837/ijccc.2019.6.3692.

Повний текст джерела

Анотація:

This research article uses a Fuzzy Cognitive Map (FCM) approach to improve an earlier proposed IQ test characteristics of Artificial Intelligence (AI) systems. The defuzzification process makes use of fuzzy logic and the triangular membership function along with linguistic term analyses. Each edge of the proposed FCM is assigned to a positive or negative influence type associated with a quantitative weight. All the weights are based on the defuzzified value in the defuzzification results. This research also leverages a dynamic scenario analysis to investigate the interrelationships between driver concepts and other concepts. Worst and best-case scenarios have been conducted on the correlation among concepts. We also use an inference simulation to examine the concepts importance order and the FCM convergence status. The analysis results not only examine the FCM complexity, but also draws insightful conclusions.

Стилі APA, Harvard, Vancouver, ISO та ін.

Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!