Log in

Relevant bibliographies by topics / Polynomial-time algorithms

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers
Reports

Academic literature on the topic 'Polynomial-time algorithms'

Author: Grafiati

Published: 4 June 2021

Last updated: 25 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Polynomial-time algorithms.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Polynomial-time algorithms"

1

Saxena, Vatsal. "Analysis of Polynomial Time and Non-Polynomial Time of Algorithms." International Journal for Research in Applied Science and Engineering Technology 11, no. 5 (May 31, 2023): 3311–16. http://dx.doi.org/10.22214/ijraset.2023.52268.

Full text

Abstract:

Abstract: The P vs NP problem is one of the most significant open problems in computer science and mathematics. This problem asks whether every problem that can be solved in polynomial time can also be verified in polynomial time. The purpose of this research paper is to explore the P vs NP problem and its relevance in the analysis of algorithms. We will discuss the techniques used to design and analyze algorithms, such as divide-and-conquer, dynamic programming, and greedy algorithms, and their relation to the P vs NP problem. We will also examine some examples of polynomial-time algorithms and NP-hard problems and analyze their time and space complexity, addition to which we will analyze the NP-Complete Problem and finally looking the current scenario of the P & NP and stating its significance.

APA, Harvard, Vancouver, ISO, and other styles

2

TANAKA, Hisao, and Masafumi KUDOH. "On relativized probabilistic polynomial time algorithms." Journal of the Mathematical Society of Japan 49, no. 1 (January 1997): 15–30. http://dx.doi.org/10.2969/jmsj/04910015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Haugland, Dag, and Eligius M. T. Hendrix. "Pooling Problems with Polynomial-Time Algorithms." Journal of Optimization Theory and Applications 170, no. 2 (February 19, 2016): 591–615. http://dx.doi.org/10.1007/s10957-016-0890-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Dadush, Dan, László A. Végh, and Giacomo Zambelli. "Geometric Rescaling Algorithms for Submodular Function Minimization." Mathematics of Operations Research 46, no. 3 (August 2021): 1081–108. http://dx.doi.org/10.1287/moor.2020.1064.

Full text

Abstract:

We present a new class of polynomial-time algorithms for submodular function minimization (SFM) as well as a unified framework to obtain strongly polynomial SFM algorithms. Our algorithms are based on simple iterative methods for the minimum-norm problem, such as the conditional gradient and Fujishige–Wolfe algorithms. We exhibit two techniques to turn simple iterative methods into polynomial-time algorithms. First, we adapt the geometric rescaling technique, which has recently gained attention in linear programming, to SFM and obtain a weakly polynomial bound [Formula: see text]. Second, we exhibit a general combinatorial black box approach to turn [Formula: see text]-approximate SFM oracles into strongly polynomial exact SFM algorithms. This framework can be applied to a wide range of combinatorial and continuous algorithms, including pseudo-polynomial ones. In particular, we can obtain strongly polynomial algorithms by a repeated application of the conditional gradient or of the Fujishige–Wolfe algorithm. Combined with the geometric rescaling technique, the black box approach provides an [Formula: see text] algorithm. Finally, we show that one of the techniques we develop in the paper can also be combined with the cutting-plane method of Lee et al., yielding a simplified variant of their [Formula: see text] algorithm.

APA, Harvard, Vancouver, ISO, and other styles

5

STEWART, IAIN A. "ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM." International Journal of Foundations of Computer Science 04, no. 02 (June 1993): 117–33. http://dx.doi.org/10.1142/s0129054193000080.

Full text

Abstract:

We look at well-known polynomial-time approximation algorithms for the optimization problem MAX-CLIQUE (“find the size of the largest clique in a graph”) with regard to how easy it is to compute the actual cliques yielded by these approximation algorithms. We show that even for two “pretty useless” deterministic polynomial-time approximation algorithms, it is unlikely that the resulting clique can be computed efficiently in parallel. We also show that for each non-deterministic algorithm, it is unlikely that there is some deterministic polynomial-time algorithm that decides whether any given vertex appears in some clique yielded by that nondeterministic algorithm.

APA, Harvard, Vancouver, ISO, and other styles

6

Decker, Thomas, Peter Hoyer, Gabor Ivanyos, and Miklos Santha. "Polynomial time quantum algorithms for certain bivariate hidden polynomial problems." Quantum Information and Computation 14, no. 9&10 (July 2014): 790–806. http://dx.doi.org/10.26421/qic14.9-10-6.

Full text

Abstract:

We present a new method for solving the hidden polynomial graph problem (HPGP) which is a special case of the hidden polynomial problem (HPP). The new approach yields an efficient quantum algorithm for the bivariate HPGP even when the input consists of several level set superpositions, a more difficult version of the problem than the one where the input is given by an oracle. For constant degree, the algorithm is polylogarithmic in the size of the base field. We also apply the results to give an efficient quantum algorithm for the oracle version of the HPP for an interesting family of bivariate hidden functions. This family includes diagonal quadratic forms and elliptic curves.

APA, Harvard, Vancouver, ISO, and other styles

7

Ozturkoglu, Yucel, and Omer Ozturkoglu. "Propose a Polynomial Time Algorithm for Total Completion Time Objective." International Journal of Mathematical, Engineering and Management Sciences 6, no. 3 (June 1, 2021): 932–43. http://dx.doi.org/10.33889/ijmems.2021.6.3.055.

Full text

Abstract:

In this study, we integrate deteriorate jobs with repair&maintenance activity on a single machine scheduling subject to total completion time. This work has more than one motivation. First, jobs are assigned to machines in an automated production line. Later, to schedule the maintenance activities, if needed, to prevent machinery from breaking down later. There are some important mathematical models to solve this combination. However, due to the complexity of the problem which is Np-hard, a polynomial algorithm should be needed for solving large problems. Therefore, this article introduces several polnomial algorithms to determine the order of things best. With using these algorithms, it will be possible to determine where to assign to the schedule, taking into account the number of maintenance activities required and their optimum total completion time.

APA, Harvard, Vancouver, ISO, and other styles

8

Lozovanu, Dmitrii, and Stefan Pickl. "Polynomial Time Algorithms for Determining Optimal Strategies." Electronic Notes in Discrete Mathematics 13 (April 2003): 64–68. http://dx.doi.org/10.1016/s1571-0653(04)00440-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Wei, Yongmei, and Guoan Bi. "Fast algorithms for polynomial time frequency transform." Signal Processing 87, no. 5 (May 2007): 789–98. http://dx.doi.org/10.1016/j.sigpro.2006.07.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Turrini, Andrea, and Holger Hermanns. "Polynomial time decision algorithms for probabilistic automata." Information and Computation 244 (October 2015): 134–71. http://dx.doi.org/10.1016/j.ic.2015.07.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Polynomial-time algorithms"

1

Domingues, Riaal. "A polynomial time algorithm for prime recognition." Diss., Pretoria : [s.n.], 2006. http://upetd.up.ac.za/thesis/available/etd-08212007-100529.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

朱紫君 and Chi-kwan Chu. "Polynomial time algorithms for linear and integer programming." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2000. http://hub.hku.hk/bib/B31224301.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Chu, Chi-kwan. "Polynomial time algorithms for linear and integer programming." Hong Kong : University of Hong Kong, 2000. http://sunzi.lib.hku.hk/hkuto/record.jsp?B22718710.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Boljunčić, Jadranka. "Quadratic programming : quantitative analysis and polynomial running time algorithms." Thesis, University of British Columbia, 1987. http://hdl.handle.net/2429/27532.

Full text

Abstract:

Many problems in economics, statistics and numerical analysis can be formulated as the optimization of a convex quadratic function over a polyhedral set. A polynomial algorithm for solving convex quadratic programming problems was first developed by Kozlov at al. (1979). Tardos (1986) was the first to present a polynomial algorithm for solving linear programming problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand side and the cost coefficients. In the first part of the thesis we extended Tardos' results to strictly convex quadratic programming of the form max {cTx-½xTDx : Ax ≤ b, x ≥0} with D being symmetric positive definite matrix. In our algorithm the number of arithmetic steps is independent of c and b but depends on the size of the entries of the matrices A and D. Another part of the thesis is concerned with proximity and sensitivity of integer and mixed-integer quadratic programs. We have shown that for any optimal solution z̅ for a given separable quadratic integer programming problem there exist an optimal solution x̅ for its continuous relaxation such that
z̅ - x̅
∞≤n∆(A) where n is the number of variables and ∆(A) is the largest absolute sub-determinant of the integer constraint matrix A . We have further shown that for any feasible solution z, which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution z̅ having greater objective function value and with
z - z̅
∞≤n∆(A). Under some additional assumptions the distance between a pair of optimal solutions to the integer quadratic programming problem with right hand side vectors b and b', respectively, depends linearly on
b — b'
₁. The extension to the mixed-integer nonseparable quadratic case is also given. Some sensitivity analysis results for nonlinear integer programming problems are given. We assume that the nonlinear 0 — 1 problem was solved by implicit enumeration and that some small changes have been made in the right hand side or objective function coefficients. We then established what additional information to keep in the implicit enumeration tree, when solving the original problem, in order to provide us with bounds on the optimal value of a perturbed problem. Also, suppose that after solving the original problem to optimality the problem was enlarged by introducing a new 0 — 1 variable, say xn+1. We determined a lower bound on the added objective function coefficients for which the new integer variable xn+1 remains at zero level in the optimal solution for the modified integer nonlinear program. We discuss the extensions to the mixed-integer case as well as to the case when integer variables are not restricted to be 0 or 1. The computational results for an example with quadratic objective function, linear constraints and 0—1 variables are provided. Finally, we have shown how to replace the objective function of a quadratic program with 0—1 variables ( by an integer objective function whose size is polynomially bounded by the number of variables) without changing the set of optimal solutions. This was done by making use of the algorithm given by Frank and Tardos (1985) which in turn uses the simultaneous approximation algorithm of Lenstra, Lenstra and Lovász (1982).
Business, Sauder School of
Graduate

APA, Harvard, Vancouver, ISO, and other styles

5

Regan, K. W. "On the separation of complexity classes." Thesis, University of Oxford, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.375305.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Pardella, Gregor L. [Verfasser]. "Efficient Polynomial-Time Algorithms for Special Graph Partitioning Problems / Gregor L. Pardella." München : Verlag Dr. Hut, 2011. http://d-nb.info/1015604919/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Anderson, Robert Lawrence. "An Exposition of the Deterministic Polynomial-Time Primality Testing Algorithm of Agrawal-Kayal-Saxena." Diss., CLICK HERE for online access, 2005. http://contentdm.lib.byu.edu/ETD/image/etd869.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Cuvelier, Thibaut. "Polynomial-Time Algorithms for Combinatorial Semibandits : Computationally Tractable Reinforcement Learning in Complex Environments." Electronic Thesis or Diss., université Paris-Saclay, 2021. http://www.theses.fr/2021UPASG020.

Full text

Abstract:

La prise de décision séquentielle est une composante essentielle de nombreuses applications, de la gestion des réseaux informatiques aux annonces en ligne. L'outil principal est l'apprentissage par renforcement : un agent prend une séquence de décisions afin d'atteindre son objectif, avec des mesures typiquement bruitées de son environnement. Par exemple, un agent peut contrôler une voiture autonome; l'environnement est la ville dans laquelle la voiture se déplace. Les problèmes de bandits forment une classe d'apprentissage de renforcement pour laquelle on peut démontrer de très forts résultats théoriques. Les algorithmes de bandits se concentrent sur le dilemme exploration-exploitation : pour avoir une bonne performance, l'agent doit avoir une connaissance approfondie de son environnement (exploration) ; cependant, il doit aussi jouer des actions qui le rapprochent de son but (exploitation).Dans cette thèse, nous nous concentrons sur les bandits combinatoires, qui sont des bandits dont les décisions sont très structurées (une structure "combinatoire"). Il s'agit notamment des cas où l'agent détermine un chemin à suivre (sur une route, dans un réseau informatique, etc.) ou des publicités à afficher sur un site Web. De telles situations partagent leur complexité algorithmique : alors qu'il est souvent facile de déterminer la décision optimale lorsque les paramètres sont connus (le temps pour traverser une route, le profit généré par l'affichage d'une publicité à un endroit donné), la variante bandit (lorsque les paramètres doivent être déterminés par des interactions avec l'environnement) est bien plus complexe.Nous proposons deux nouveaux algorithmes pour aborder ces problèmes par des techniques d'optimisation mathématique. Basés sur des hypothèses faibles, ils présentent une complexité temporelle polynomiale, tout en étant performants par rapport aux algorithmes de pointe pour les mêmes problèmes. Ils présentent également d'excellentes propriétés statistiques, ce qui signifie qu'ils trouvent un équilibre entre exploration et exploitation proche de l'optimum théorique. Les travaux précédents sur les bandits combinatoires ont dû faire un choix entre le temps de calcul et la performance statistique ; nos algorithmes montrent que ce dilemme n'a pas lieu d'être
Sequential decision making is a core component of many real-world applications, from computer-network operations to online ads. The major tool for this use is reinforcement learning: an agent takes a sequence of decisions in order to achieve its goal, with typically noisy measurements of the evolution of the environment. For instance, a self-driving car can be controlled by such an agent; the environment is the city in which the car manœuvers. Bandit problems are a class of reinforcement learning for which very strong theoretical properties can be shown. The focus of bandit algorithms is on the exploration-exploitation dilemma: in order to have good performance, the agent must have a deep knowledge of its environment (exploration); however, it should also play actions that bring it closer to its goal (exploitation).In this dissertation, we focus on combinatorial bandits, which are bandits whose decisions are highly structured (a "combinatorial" structure). These include cases where the learning agent determines a path to follow (on a road, in a computer network, etc.) or ads to display on a Website. Such situations share their computational complexity: while it is often easy to determine the optimum decision when the parameters are known (the time to cross a road, the monetary gain of displaying an ad at a given place), the bandit variant (when the parameters must be determined through interactions with the environment) is more complex.We propose two new algorithms to tackle these problems by mathematical-optimisation techniques. Based on weak hypotheses, they have a polynomial time complexity, and yet perform well compared to state-of-the-art algorithms for the same problems. They also enjoy excellent statistical properties, meaning that they find a balance between exploration and exploitation that is close to the theoretical optimum. Previous work on combinatorial bandits had to make a choice between computational burden and statistical performance; our algorithms show that there is no need for such a quandary

APA, Harvard, Vancouver, ISO, and other styles

9

Heednacram, Apichat. "The NP-Hardness of Covering Points with Lines, Paths and Tours and their Tractability with FPT-Algorithms." Thesis, Griffith University, 2010. http://hdl.handle.net/10072/367754.

Full text

Abstract:

Given a problem for which no polynomial-time algorithm is likely to exist, we investigate how to attack this seemingly intractable problem based on parameterized complexity theory. We study hard geometric problems, and show that they are xed-parameter tractable (FPT) given an instance and a parameter k. This allows the problems to be solved exactly, rather than approximately, in polynomial time in the size of the input and exponential time in the parameter. Although the parameterized approach is still young, in recent years, there have been many results published concerning graph problems and databases. However, not many earlier results apply the parameterized approach in the eld of computational geometry. This thesis, therefore, focuses on geometric NP-hard problems. These problems are the Line Cover problem, the Rectilinear Line Cover problem in higher dimensions, the Rectilinear Minimum-Links Spanning Path problem in higher dimensions, the Rectilinear Hyper- plane Cover problem, the Minimum-Bends Traveling Salesman Prob- lem and the Rectilinear Minimum-Bends Traveling Salesman Prob- lem, in addition to some other variants of these problems. The Rectilinear Minimum-Links Spanning Path problem in higher dimensions and the Rectilinear Hyperplane Cover problem had been the subject of only conjectures about their intractability. Therefore, we present the NP-completeness proofs for these problems. After verifying their hardness, we use the xed-parameter approach to solve the two problems. We focus on solving the decision version of the problems, rather than solving the optimizations. However, with the Line Cover problem we demonstrate that it is not dicult to adapt algorithms for the decision version to algorithms for the optimization version. We also implement several algorithms for the Line Cover problem and conduct experimental evaluations of our algorithms with respect to previously known algorithms. For the remaining problems in the thesis, we will establish only the fundamental results. That is, we determine xed-parameter tractability of those problems.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Information and Communication Technology
Science, Environment, Engineering and Technology
Full Text

APA, Harvard, Vancouver, ISO, and other styles

10

Van-'T-Hof, Pim. "Exploiting structure to cope with NP-hard graph problems : polynomial and exponential time exact algorithms." Thesis, Durham University, 2010. http://etheses.dur.ac.uk/285/.

Full text

Abstract:

An ideal algorithm for solving a particular problem always finds an optimal solution, finds such a solution for every possible instance, and finds it in polynomial time. When dealing with NP-hard problems, algorithms can only be expected to possess at most two out of these three desirable properties. All algorithms presented in this thesis are exact algorithms, which means that they always find an optimal solution. Demanding the solution to be optimal means that other concessions have to be made when designing an exact algorithm for an NP-hard problem: we either have to impose restrictions on the instances of the problem in order to achieve a polynomial time complexity, or we have to abandon the requirement that the worst-case running time has to be polynomial. In some cases, when the problem under consideration remains NP-hard on restricted input, we are even forced to do both. Most of the problems studied in this thesis deal with partitioning the vertex set of a given graph. In the other problems the task is to find certain types of paths and cycles in graphs. The problems all have in common that they are NP-hard on general graphs. We present several polynomial time algorithms for solving restrictions of these problems to specific graph classes, in particular graphs without long induced paths, chordal graphs and claw-free graphs. For problems that remain NP-hard even on restricted input we present exact exponential time algorithms. In the design of each of our algorithms, structural graph properties have been heavily exploited. Apart from using existing structural results, we prove new structural properties of certain types of graphs in order to obtain our algorithmic results.

APA, Harvard, Vancouver, ISO, and other styles

More sources

Books on the topic "Polynomial-time algorithms"

1

Kogan, Konstantin, and Eugene Khmelnitsky. Scheduling: Control-Based Theory and Polynomial-Time Algorithms. Boston, MA: Springer US, 2000. http://dx.doi.org/10.1007/978-1-4615-4675-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Kogan, Konstantin. Scheduling: Control-based theory and polynomial-time algorithms. Dordrecht: Kluwer Academic Publishers, 2000.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

3

Jerrum, Mark. Polynomial-time approximation algorithms for the Ising model. Edinburgh: University of Edinburgh Department of Computer Science, 1990.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

4

Tovey, Craig A. A polynomial-time algorithm for computing the yolk in fixed dimension. Monterey, Calif: Naval Postgraduate School, 1991.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

5

Gore, Vivek. A quasi-polynomial-time algorithm for sampling words from a context-free language. Edinburgh: LFCS, Dept. of Computer Science, University of Edinburgh, 1995.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

6

Hirshfeld, Yoram. A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes. Edinburgh: LFCS, Dept. of Computer Science, University of Edinburgh, 1994.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

7

Schimanski, Stefan. Polynomial Time Calculi. Lulu Press, Inc., 2009.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

8

Kogan, K., and E. Khmelnitsky. Scheduling: Control-Based Theory and Polynomial-Time Algorithms. Springer London, Limited, 2013.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

9

Kogan, K., and Eugene Khmelnitsky. Scheduling: Control-Based Theory and Polynomial-Time Algorithms. Springer, 2014.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

10

Kogan, K., and Eugene Khmelnitsky. Scheduling: Control-Based Theory And Polynomial-Time Algorithms. Springer, 2013.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Polynomial-time algorithms"

1

Bhattacharyya, Arnab. "Polynomial Decompositions in Polynomial Time." In Algorithms - ESA 2014, 125–36. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014. http://dx.doi.org/10.1007/978-3-662-44777-2_11.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Chakradhar, Srimat T., Vishwani D. Agrawal, and Michael L. Bushneil. "Polynomial-time Testability." In Neural Models and Algorithms for Digital Testing, 123–39. Boston, MA: Springer US, 1991. http://dx.doi.org/10.1007/978-1-4615-3958-2_11.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Bonsma, Paul, and Felix Breuer. "Finding Fullerene Patches in Polynomial Time." In Algorithms and Computation, 750–59. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-10631-6_76.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

List, Nikolas, and Hans Ulrich Simon. "General Polynomial Time Decomposition Algorithms." In Learning Theory, 308–22. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11503415_21.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Dietzfelbinger, Martin. "2. Algorithms for Numbers and Their Complexity." In Primality Testing in Polynomial Time, 13–21. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-25933-6_2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Baptiste, Philippe, Marek Chrobak, and Christoph Dürr. "Polynomial Time Algorithms for Minimum Energy Scheduling." In Algorithms – ESA 2007, 136–50. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. http://dx.doi.org/10.1007/978-3-540-75520-3_14.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Kamiński, Marcin, Daniël Paulusma, and Dimitrios M. Thilikos. "Contractions of Planar Graphs in Polynomial Time." In Algorithms – ESA 2010, 122–33. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-15775-2_11.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Furer, Martin, C. R. Subramanian, and C. E. Veni Madhavan. "Coloring random graphs in polynomial expected time." In Algorithms and Computation, 31–37. Berlin, Heidelberg: Springer Berlin Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-57568-5_232.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Konyagin, Sergei, and Carl Pomerance. "On Primes Recognizable in Deterministic Polynomial Time." In Algorithms and Combinatorics, 176–98. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. http://dx.doi.org/10.1007/978-3-642-60408-9_15.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Hemachandra, Lane A. "Algorithms from complexity theory: Polynomial-time operations for complex sets." In Algorithms, 221–31. Berlin, Heidelberg: Springer Berlin Heidelberg, 1990. http://dx.doi.org/10.1007/3-540-52921-7_71.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Polynomial-time algorithms"

1

Sanders, Peter, Sebastian Egner, and Ludo Tolhuizen. "Polynomial time algorithms for network information flow." In the fifteenth annual ACM symposium. New York, New York, USA: ACM Press, 2003. http://dx.doi.org/10.1145/777412.777464.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Golin, Mordecai, and Elfarouk Harb. "Polynomial Time Algorithms for Constructing Optimal AIFV Codes." In 2019 Data Compression Conference (DCC). IEEE, 2019. http://dx.doi.org/10.1109/dcc.2019.00031.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Roy, Kaushik, Alexandre Bayen, and Claire Tomlin. "Polynomial Time Algorithms for Scheduling of Arrival Aircraft." In AIAA Guidance, Navigation, and Control Conference and Exhibit. Reston, Virigina: American Institute of Aeronautics and Astronautics, 2005. http://dx.doi.org/10.2514/6.2005-6044.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Izumi, Taisuke, Naoki Kitamura, Takamasa Naruse, and Gregory Schwartzman. "Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs." In SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures. New York, NY, USA: ACM, 2022. http://dx.doi.org/10.1145/3490148.3538590.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Coleman, Tom, and Anthony Wirth. "A Polynomial Time Approximation Scheme for k-Consensus Clustering." In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2010. http://dx.doi.org/10.1137/1.9781611973075.59.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Bateni, Mohammad Hossein, Mohammad Taghi Hajiaghayi, Philip N. Klein, and Claire Mathieu. "A Polynomial-time Approximation Scheme for Planar Multiway Cut." In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2012. http://dx.doi.org/10.1137/1.9781611973099.54.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Lokshantov, Daniel, Martin Vatshelle, and Yngve Villanger. "Independent Set in P5-Free Graphs in Polynomial Time." In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2013. http://dx.doi.org/10.1137/1.9781611973402.43.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Chistov, Alexander, Gábor Ivanyos, and Marek Karpinski. "Polynomial time algorithms for modules over finite dimensional algebras." In the 1997 international symposium. New York, New York, USA: ACM Press, 1997. http://dx.doi.org/10.1145/258726.258751.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Cuvelier, Thibaut, Richard Combes, and Eric Gourdin. "Statistically Efficient, Polynomial-Time Algorithms for Combinatorial Semi-Bandits." In SIGMETRICS '21: ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. New York, NY, USA: ACM, 2021. http://dx.doi.org/10.1145/3410220.3453926.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Huang, Jun, and Yoshiaki Tanaka. "QoS routing algorithms using fully polynomial time approximation scheme." In 2011 IEEE 19th International Workshop on Quality of Service (IWQoS). IEEE, 2011. http://dx.doi.org/10.1109/iwqos.2011.5931329.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Polynomial-time algorithms"

1

Borgwardt, Stefan, Walter Forkel, and Alisa Kovtunova. Finding New Diamonds: Temporal Minimal-World Query Answering over Sparse ABoxes. Technische Universität Dresden, 2019. http://dx.doi.org/10.25368/2023.223.

Full text

Abstract:

Lightweight temporal ontology languages have become a very active field of research in recent years. Many real-world applications, like processing electronic health records (EHRs), inherently contain a temporal dimension, and require efficient reasoning algorithms. Moreover, since medical data is not recorded on a regular basis, reasoners must deal with sparse data with potentially large temporal gaps. In this paper, we introduce a temporal extension of the tractable language ELH⊥, which features a new class of convex diamond operators that can be used to bridge temporal gaps. We develop a completion algorithm for our logic, which shows that entailment remains tractable. Based on this, we develop a minimal-world semantics for answering metric temporal conjunctive queries with negation. We show that query answering is combined first-order rewritable, and hence in polynomial time in data complexity.

APA, Harvard, Vancouver, ISO, and other styles

2

Küsters, Ralf, and Alex Borgida. What's in an Attribute? Consequences for the Least Common Subsumer. Aachen University of Technology, 1999. http://dx.doi.org/10.25368/2022.102.

Full text

Abstract:

Functional relationships between objects, called 'attributes', are of considerable importance in knowledge representation languages, including Description Logics (DLs). A study of the literature indicates that papers have made, often implicity, different assumptions about the nature of attributes: whether they are always required to have a value, or whether they can be partial functions. The work presented here is the first explicit study of this difference for (sub-)classes of the CLASSIC DL, involving the same-as concept constructor. It is shown that although determining subsumption between concept descriptions has the same complexity (though requiring different algorithms), the story is different in the case of determining the least common subsumer (lcs). For attributes interpreted as partial functions, the lcs exists and can be computed relatively easily; even in this case our results correct and extend three previous papers about the lcs of DLs. In the case where attributes must have a value, the lcs may not exist, and even if it exists it may be of exponential size. Interestingly, it is possible to decide in polynomial time if the lcs exists.

APA, Harvard, Vancouver, ISO, and other styles

3

Tseng, Paul. A Very Simple Polynomial-Time Algorithm for Linear Programming. Fort Belvoir, VA: Defense Technical Information Center, September 1988. http://dx.doi.org/10.21236/ada202502.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Tovey, Craig A. A Polynomial-Time Algorithm for Computing the Yolk in Fixed Dimension. Fort Belvoir, VA: Defense Technical Information Center, August 1991. http://dx.doi.org/10.21236/ada240060.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Peñaloza, Rafael, and Anni-Yasmin Turhan. Completion-based computation of most specific concepts with limited role-depth for EL and Prob-EL⁰¹. Technische Universität Dresden, 2010. http://dx.doi.org/10.25368/2022.176.

Full text

Abstract:

In Description Logics the reasoning service most specific concept (msc) constructs a concept description that generalizes an ABox individual into a concept description. For the Description Logic EL the msc may not exist, if computed with respect to general EL-TBoxes or cyclic ABoxes. However, it is still possible to find a concept description that is the msc up to a fixed role-depth, i.e. with respect to a maximal nesting of quantifiers. In this report we present a practical approach for computing the roledepth bounded msc, based on the polynomial-time completion algorithm for EL. We extend these methods to Prob-EL⁰¹c , which is a probabilistic variant of EL. Together with the companion report [9] this report devises computation methods for the bottom-up construction of knowledge bases for EL and Prob-EL⁰¹c .

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!