Log in

Relevant bibliographies by topics / Polynomial-time algorithms / Journal articles

To see the other types of publications on this topic, follow the link: Polynomial-time algorithms.

Journal articles 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 top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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

11

Baptiste, Philippe, Marek Chrobak, and Christoph Dürr. "Polynomial-time algorithms for minimum energy scheduling." ACM Transactions on Algorithms 8, no. 3 (July 2012): 1–29. http://dx.doi.org/10.1145/2229163.2229170.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Fukuda, Komei, and Antoine Musitelli. "New polynomial-time algorithms for Camion bases." Discrete Mathematics 306, no. 24 (December 2006): 3302–6. http://dx.doi.org/10.1016/j.disc.2006.06.015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Nesterov, Yu E. "Polynomial-time dual algorithms in linear programming." Cybernetics 25, no. 1 (1989): 40–49. http://dx.doi.org/10.1007/bf01074882.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Cohen, Fraigniaud, and Mitjana. "Polynomial-Time Algorithms for Minimum-Time Broadcast in Trees." Theory of Computing Systems 35, no. 6 (June 18, 2002): 641–65. http://dx.doi.org/10.1007/s00224-002-1047-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Arslan, Abdullah N., Betsy George, and Kirsten Stor. "New algorithms for pattern matching with wildcards and length constraints." Discrete Mathematics, Algorithms and Applications 07, no. 03 (September 2015): 1550032. http://dx.doi.org/10.1142/s1793830915500329.

Full text

Abstract:

The pattern matching with wildcards and length constraints problem is an interesting problem in the literature whose computational complexity is still open. There are polynomial time exact algorithms for its special cases. There are heuristic algorithms, and online algorithms that do not guarantee an optimal solution to the original problem. We consider two special cases of the problem for which we develop offline solutions. We give an algorithm for one case with provably better worst case time complexity compared to existing algorithms. We present the first exact algorithm for the second case. This algorithm uses integer linear programming (ILP) and it takes polynomial time under certain conditions.

APA, Harvard, Vancouver, ISO, and other styles

16

GAWRYCHOWSKI, PAWEŁ, DALIA KRIEGER, NARAD RAMPERSAD, and JEFFREY SHALLIT. "FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME." International Journal of Foundations of Computer Science 21, no. 04 (August 2010): 597–618. http://dx.doi.org/10.1142/s0129054110007441.

Full text

Abstract:

We give an O(n + t) time algorithm to determine whether an NFA with n states and t transitions accepts a language of polynomial or exponential growth. Given an NFA accepting a language of polynomial growth, we can also determine the order of polynomial growth in O(n+t) time. We also give polynomial time algorithms to solve these problems for context-free grammars.

APA, Harvard, Vancouver, ISO, and other styles

17

Baum, Eric B. "A Proposal for More Powerful Learning Algorithms." Neural Computation 1, no. 2 (June 1989): 201–7. http://dx.doi.org/10.1162/neco.1989.1.2.201.

Full text

Abstract:

Judd (1988) and Blum and Rivest (1988) have recently proved that the loading problem for neural networks is NP complete. This makes it very unlikely that any algorithm like backpropagation which varies weights on a network of fixed size and topology will be able to learn in polynomial time. However, Valiant has recently proposed a learning protocol (Valiant 1984), which allows one to sensibly consider generalization by learning algorithms with the freedom to add neurons and synapses, as well as simply adjusting weights. Within this context, standard circuit complexity arguments show that learning algorithms with such freedom can solve in polynomial time any learning problem that can be solved in polynomial time by any algorithm whatever. In this sense, neural nets are universal learners, capable of learning any learnable class of concepts.

APA, Harvard, Vancouver, ISO, and other styles

18

Chen, Lin, Nicole Megow, Roman Rischke, Leen Stougie, and José Verschae. "Optimal algorithms for scheduling under time-of-use tariffs." Annals of Operations Research 304, no. 1-2 (April 8, 2021): 85–107. http://dx.doi.org/10.1007/s10479-021-04059-3.

Full text

Abstract:

AbstractWe consider a natural generalization of classical scheduling problems to a setting in which using a time unit for processing a job causes some time-dependent cost, the time-of-use tariff, which must be paid in addition to the standard scheduling cost. We focus on preemptive single-machine scheduling and two classical scheduling cost functions, the sum of (weighted) completion times and the maximum completion time, that is, the makespan. While these problems are easy to solve in the classical scheduling setting, they are considerably more complex when time-of-use tariffs must be considered. We contribute optimal polynomial-time algorithms and best possible approximation algorithms. For the problem of minimizing the total (weighted) completion time on a single machine, we present a polynomial-time algorithm that computes for any given sequence of jobs an optimal schedule, i.e., the optimal set of time slots to be used for preemptively scheduling jobs according to the given sequence. This result is based on dynamic programming using a subtle analysis of the structure of optimal solutions and a potential function argument. With this algorithm, we solve the unweighted problem optimally in polynomial time. For the more general problem, in which jobs may have individual weights, we develop a polynomial-time approximation scheme (PTAS) based on a dual scheduling approach introduced for scheduling on a machine of varying speed. As the weighted problem is strongly NP-hard, our PTAS is the best possible approximation we can hope for. For preemptive scheduling to minimize the makespan, we show that there is a comparably simple optimal algorithm with polynomial running time. This is true even in a certain generalized model with unrelated machines.

APA, Harvard, Vancouver, ISO, and other styles

19

Mizuno, Shinji, and Kaori Masuzawa. "POLYNOMIAL TIME INTERIOR POINT ALGORITHMS FOR TRANSPORTATION PROBLEMS." Journal of the Operations Research Society of Japan 32, no. 3 (1989): 371–82. http://dx.doi.org/10.15807/jorsj.32.371.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Mizuno, Shinji, Akiko Yoshise, and Takeshi Kikuchi. "PRACTICAL POLYNOMIAL TIME ALGORITHMS FOR LINEAR COMPLEMENTARITY PROBLEMS." Journal of the Operations Research Society of Japan 32, no. 1 (1989): 75–92. http://dx.doi.org/10.15807/jorsj.32.75.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Jaggi, S., P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. M. G. M. Tolhuizen. "Polynomial Time Algorithms for Multicast Network Code Construction." IEEE Transactions on Information Theory 51, no. 6 (June 2005): 1973–82. http://dx.doi.org/10.1109/tit.2005.847712.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Ivanyos, Gábor, Marek Karpinski, and Nitin Saxena. "Deterministic Polynomial Time Algorithms for Matrix Completion Problems." SIAM Journal on Computing 39, no. 8 (January 2010): 3736–51. http://dx.doi.org/10.1137/090781231.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Duncan, Rob, Jianbo Qian, Antoine Vigneron, and Binhai Zhu. "Polynomial time algorithms for three-label point labeling." Theoretical Computer Science 296, no. 1 (March 2003): 75–87. http://dx.doi.org/10.1016/s0304-3975(02)00433-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Strzemecki, Tadeusz. "Polynomial-time algorithms for generation of prime implicants." Journal of Complexity 8, no. 1 (March 1992): 37–63. http://dx.doi.org/10.1016/0885-064x(92)90033-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Wu, Bang Ye. "Polynomial time algorithms for some minimum latency problems." Information Processing Letters 75, no. 5 (October 2000): 225–29. http://dx.doi.org/10.1016/s0020-0190(00)00102-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Sinchev, B., A. B. Sinchev, Zh Akzhanova, Y. Issekeshev, and A. M. Mukhanova. "POLYNOMIAL TIME ALGORITHMS FOR SOLVING NP-COMPLETE PROBLEMS." NEWS of National Academy of Sciences of the Republic of Kazakhstan 3, no. 441 (June 15, 2020): 97–101. http://dx.doi.org/10.32014/2020.2518-170x.59.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Jerrum, Mark, and Alistair Sinclair. "Polynomial-Time Approximation Algorithms for the Ising Model." SIAM Journal on Computing 22, no. 5 (October 1993): 1087–116. http://dx.doi.org/10.1137/0222066.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Tung, Shih Ping. "Polynomial time algorithms for sentences over number fields." Information and Computation 97, no. 2 (April 1992): 262–76. http://dx.doi.org/10.1016/0890-5401(92)90037-g.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Cygan, M., M. Kubica, J. Radoszewski, W. Rytter, and T. Waleń. "Polynomial-time approximation algorithms for weighted LCS problem." Discrete Applied Mathematics 204 (May 2016): 38–48. http://dx.doi.org/10.1016/j.dam.2015.11.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Kashiwabara, Toshinobu, Sumio Masuda, Kazuo Nakajima, and Toshio Fujisawa. "Polynomial time algorithms on circular-arc overlap graphs." Networks 21, no. 2 (March 1991): 195–203. http://dx.doi.org/10.1002/net.3230210205.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Hermann, Miki, and Phokion G. Kolaitis. "Unification Algorithms Cannot Be Combined in Polynomial Time." Information and Computation 162, no. 1-2 (October 2000): 24–42. http://dx.doi.org/10.1006/inco.1999.2855.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Cuvelier, Thibaut, Richard Combes, and Eric Gourdin. "Statistically Efficient, Polynomial-Time Algorithms for Combinatorial Semi-Bandits." ACM SIGMETRICS Performance Evaluation Review 49, no. 1 (June 22, 2022): 5–6. http://dx.doi.org/10.1145/3543516.3453926.

Full text

Abstract:

We consider combinatorial semi-bandits over a set X ⊂ (0,1)d where rewards are uncorrelated across items. For this problem, the algorithm ESCB yields the smallest known regret bound R(T) = O ( d (łn m)2 (łn T) øver Δmin) after T rounds, where m = maxx ∈ X 1Tx. However, ESCB has computational complexity O(|X|), which is typically exponential in d, and cannot be used in large dimensions. We propose the first algorithm that is both computationally and statistically efficient for this problem with regret R(T) = O (d (łn m)2 (łn T)øver Δmin) and computational asymptotic complexity O( δT-1 poly (d)), where δT is a function which vanishes arbitrarily slowly. Our approach involves carefully designing AESCB, an approximate version of ESCB with the same regret guarantees. We show that, whenever budgeted linear maximization over X can be solved up to a given approximation ratio, AESCB is implementable in polynomial time O (δT-1 poly (d)) by repeatedly maximizing a linear function over X subject to a linear budget constraint, and showing how to solve these maximization problems efficiently. Additional algorithms, proofs and numerical experiments are given in the complete version of this work.

APA, Harvard, Vancouver, ISO, and other styles

33

Paschos, Vangelis. "An overview on polynomial approximation of NP-hard problems." Yugoslav Journal of Operations Research 19, no. 1 (2009): 3–40. http://dx.doi.org/10.2298/yjor0901003p.

Full text

Abstract:

The fact that polynomial time algorithm is very unlikely to be devised for an optimal solving of the NP-hard problems strongly motivates both the researchers and the practitioners to try to solve such problems heuristically, by making a trade-off between computational time and solution's quality. In other words, heuristic computation consists of trying to find not the best solution but one solution which is 'close to' the optimal one in reasonable time. Among the classes of heuristic methods for NP-hard problems, the polynomial approximation algorithms aim at solving a given NP-hard problem in poly-nomial time by computing feasible solutions that are, under some predefined criterion, as near to the optimal ones as possible. The polynomial approximation theory deals with the study of such algorithms. This survey first presents and analyzes time approximation algorithms for some classical examples of NP-hard problems. Secondly, it shows how classical notions and tools of complexity theory, such as polynomial reductions, can be matched with polynomial approximation in order to devise structural results for NP-hard optimization problems. Finally, it presents a quick description of what is commonly called inapproximability results. Such results provide limits on the approximability of the problems tackled.

APA, Harvard, Vancouver, ISO, and other styles

34

Talmaciu, Mihai, and Elena Nechita. "On Polar, Trivially Perfect Graphs." International Journal of Computers Communications & Control 5, no. 5 (December 1, 2010): 939. http://dx.doi.org/10.15837/ijccc.2010.5.2257.

Full text

Abstract:

<p>During the last decades, different types of decompositions have been processed in the field of graph theory. In various problems, for example in the construction of recognition algorithms, frequently appears the so-called weakly decomposition of graphs.<br />Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. Recognizing a polar graph is known to be NP-complete. For this class of graphs, polynomial algorithms for the maximum stable set problem are unknown and algorithms for the dominating set problem are also NP-complete.<br />In this paper we characterize the polar graphs using the weakly decomposition, give a polynomial time algorithm for recognizing graphs that are both trivially perfect and polar, and directly calculate the domination number. For the stability number and clique number, we give polynomial time algorithms. </p>

APA, Harvard, Vancouver, ISO, and other styles

35

ALDIS, JOHN W. "A POLYNOMIAL TIME ALGORITHM TO DETERMINE MAXIMAL BALANCED EQUIVALENCE RELATIONS." International Journal of Bifurcation and Chaos 18, no. 02 (February 2008): 407–27. http://dx.doi.org/10.1142/s0218127408020367.

Full text

Abstract:

Following Golubitsky, Stewart, and others, we give definitions of networks and input trees. In order to make our work as general as possible, we work with a somewhat extended notion of multiplicity, and introduce the concept of "bunching" of trees. We then define balanced equivalence relations on networks, and a partial ordering on these relations. Previous work has shown that there is a maximal balanced equivalence relation on networks of certain classes: we provide a different style of proof which gives this result for any network. We define two algorithms to determine this relation in practice on a given finite network — one for use with networks with all multiplicities equal, and a second for the more general case. We then provide illustrative examples of each algorithm in use. We show both of these algorithms to be quartic in the size of the given network.

APA, Harvard, Vancouver, ISO, and other styles

36

RAJASEKARAN, SANGUTHEVAR, and VAMSI KUNDETI. "SPECTRUM BASED TECHNIQUES FOR GRAPH ISOMORPHISM." International Journal of Foundations of Computer Science 20, no. 03 (June 2009): 479–99. http://dx.doi.org/10.1142/s0129054109006693.

Full text

Abstract:

The graph isomorphism problem is to check if two given graphs are isomorphic. Graph isomorphism is a well studied problem and numerous algorithms are available for its solution. In this paper we present algorithms for graph isomorphism that employ the spectra of graphs. An open problem that has fascinated many a scientist is if there exists a polynomial time algorithm for graph isomorphism. Though we do not solve this problem in this paper, the algorithms we present take polynomial time. These algorithms have been tested on a good collection of instances. However, we have not been able to prove that our algorithms will work on all possible instances. In this paper, we also give a new construction for cospectral graphs.

APA, Harvard, Vancouver, ISO, and other styles

37

Kuroki, Yuko, Liyuan Xu, Atsushi Miyauchi, Junya Honda, and Masashi Sugiyama. "Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback." Neural Computation 32, no. 9 (September 2020): 1733–73. http://dx.doi.org/10.1162/neco_a_01299.

Full text

Abstract:

We study the problem of stochastic multiple-arm identification, where an agent sequentially explores a size-[Formula: see text] subset of arms (also known as a super arm) from given [Formula: see text] arms and tries to identify the best super arm. Most work so far has considered the semi-bandit setting, where the agent can observe the reward of each pulled arm or assumed each arm can be queried at each round. However, in real-world applications, it is costly or sometimes impossible to observe a reward of individual arms. In this study, we tackle the full-bandit setting, where only a noisy observation of the total sum of a super arm is given at each pull. Although our problem can be regarded as an instance of the best arm identification in linear bandits, a naive approach based on linear bandits is computationally infeasible since the number of super arms [Formula: see text] is exponential. To cope with this problem, we first design a polynomial-time approximation algorithm for a 0-1 quadratic programming problem arising in confidence ellipsoid maximization. Based on our approximation algorithm, we propose a bandit algorithm whose computation time is [Formula: see text](log [Formula: see text]), thereby achieving an exponential speedup over linear bandit algorithms. We provide a sample complexity upper bound that is still worst-case optimal. Finally, we conduct experiments on large-scale data sets with more than 10[Formula: see text] super arms, demonstrating the superiority of our algorithms in terms of both the computation time and the sample complexity.

APA, Harvard, Vancouver, ISO, and other styles

38

ALLAUZEN, CYRIL, MEHRYAR MOHRI, and ASHISH RASTOGI. "GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS." International Journal of Foundations of Computer Science 22, no. 04 (June 2011): 883–904. http://dx.doi.org/10.1142/s0129054111008477.

Full text

Abstract:

We present efficient algorithms for testing the finite, polynomial, and exponential ambiguity of finite automata with ε-transitions. We give an algorithm for testing the exponential ambiguity of an automaton A in time [Formula: see text], and finite or polynomial ambiguity in time [Formula: see text], where |A|E denotes the number of transitions of A. These complexities significantly improve over the previous best complexities given for the same problem. Furthermore, the algorithms presented are simple and based on a general algorithm for the composition or intersection of automata. Additionally, we give an algorithm to determine in time [Formula: see text] the degree of polynomial ambiguity of a polynomially ambiguous automaton A and present an application of our algorithms to an approximate computation of the entropy of a probabilistic automaton. We also study the double-tape ambiguity of finite-state transducers. We show that the general problem is undecidable and that it is NP-hard for acyclic transducers. We present a specific analysis of the double-tape ambiguity of transducers with bounded delay. In particular, we give a characterization of double-tape ambiguity for synchronized transducers with zero delay that can be tested in quadratic time and give an algorithm for testing the double-tape ambiguity of transducers with bounded delay.

APA, Harvard, Vancouver, ISO, and other styles

39

Adelson-Velsky, George M., Alexander Gelbukh, and Eugene Levner. "On fast path-finding algorithms in AND-OR graphs." Mathematical Problems in Engineering 8, no. 4-5 (2002): 283–93. http://dx.doi.org/10.1080/10241230306728.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Deligkas, Argyrios, John Fearnley, and Paul Spirakis. "Lipschitz Continuity and Approximate Equilibria." Algorithmica 82, no. 10 (April 25, 2020): 2927–54. http://dx.doi.org/10.1007/s00453-020-00709-3.

Full text

Abstract:

Abstract In this paper, we study games with continuous action spaces and non-linear payoff functions. Our key insight is that Lipschitz continuity of the payoff function allows us to provide algorithms for finding approximate equilibria in these games. We begin by studying Lipschitz games, which encompass, for example, all concave games with Lipschitz continuous payoff functions. We provide an efficient algorithm for computing approximate equilibria in these games. Then we turn our attention to penalty games, which encompass biased games and games in which players take risk into account. Here we show that if the penalty function is Lipschitz continuous, then we can provide a quasi-polynomial time approximation scheme. Finally, we study distance biased games, where we present simple strongly polynomial time algorithms for finding best responses in $$L_1$$ L 1 and $$L_2^2$$ L 2 2 biased games, and then use these algorithms to provide strongly polynomial algorithms that find 2/3 and 5/7 approximate equilibria for these norms, respectively.

APA, Harvard, Vancouver, ISO, and other styles

41

Cuvelier, Thibaut, Richard Combes, and Eric Gourdin. "Statistically Efficient, Polynomial-Time Algorithms for Combinatorial Semi-Bandits." Proceedings of the ACM on Measurement and Analysis of Computing Systems 5, no. 1 (February 18, 2021): 1–31. http://dx.doi.org/10.1145/3447387.

Full text

Abstract:

We consider combinatorial semi-bandits over a set of arms X \subset \0,1\ ^d where rewards are uncorrelated across items. For this problem, the algorithm ESCB yields the smallest known regret bound R(T) = O( d (łn m)^2 (łn T) / Δ_\min ) after T rounds, where m = \max_x \in X 1^\top x. However, ESCB it has computational complexity O(|X|), which is typically exponential in d, and cannot be used in large dimensions. We propose the first algorithm that is both computationally and statistically efficient for this problem with regret R(T) = O( d (łn m)^2 (łn T) / Δ_\min ) and computational asymptotic complexity O(δ_T^-1 poly(d)), where δ_T is a function which vanishes arbitrarily slowly. Our approach involves carefully designing AESCB, an approximate version of ESCB with the same regret guarantees. We show that, whenever budgeted linear maximization over X can be solved up to a given approximation ratio, AESCB is implementable in polynomial time O(δ_T^-1 poly(d)) by repeatedly maximizing a linear function over X subject to a linear budget constraint, and showing how to solve these maximization problems efficiently.

APA, Harvard, Vancouver, ISO, and other styles

42

SUDO, Yuichi, Toshimitsu MASUZAWA, Gen MOTOYOSHI, and Tutomu MURASE. "Pseudo Polynomial Time Algorithms for Optimal Longcut Route Selection." IEICE Transactions on Information and Systems E98.D, no. 3 (2015): 607–16. http://dx.doi.org/10.1587/transinf.2014edp7278.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Guoliang Xue, Weiyi Zhang, Jian Tang, and K. Thulasiraman. "Polynomial Time Approximation Algorithms for Multi-Constrained QoS Routing." IEEE/ACM Transactions on Networking 16, no. 3 (June 2008): 656–69. http://dx.doi.org/10.1109/tnet.2007.900712.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Cui, Yun, Jesper Jansson, and Wing-Kin Sung. "Polynomial-Time Algorithms for Building a Consensus MUL-Tree." Journal of Computational Biology 19, no. 9 (September 2012): 1073–88. http://dx.doi.org/10.1089/cmb.2012.0008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Guan, Yongpei, and Andrew J. Miller. "Polynomial-Time Algorithms for Stochastic Uncapacitated Lot-Sizing Problems." Operations Research 56, no. 5 (October 2008): 1172–83. http://dx.doi.org/10.1287/opre.1070.0479.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Sridharan, Sriraman. "Polynomial time algorithms for two classes of subgraph problem." RAIRO - Operations Research 42, no. 3 (July 2008): 291–98. http://dx.doi.org/10.1051/ro:2008015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Ju, Yingtuo, and Guoan Bi. "Generalized Fast Algorithms for the Polynomial Time-Frequency Transform." IEEE Transactions on Signal Processing 55, no. 10 (October 2007): 4907–15. http://dx.doi.org/10.1109/tsp.2007.896102.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Naderi, B., M. Zandieh, and M. Yazdani. "Polynomial time approximation algorithms for proportionate open-shop scheduling." International Transactions in Operational Research 21, no. 6 (April 17, 2014): 1031–44. http://dx.doi.org/10.1111/itor.12087.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Bi, Guoan, and Yingtuo Ju. "Radix-3 fast algorithms for polynomial time frequency transforms." Signal Processing 88, no. 9 (September 2008): 2316–22. http://dx.doi.org/10.1016/j.sigpro.2008.03.018.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Kao, Ming-Yang, Henry C. M. Leung, He Sun, and Yong Zhang. "Deterministic polynomial-time algorithms for designing short DNA words." Theoretical Computer Science 494 (July 2013): 144–60. http://dx.doi.org/10.1016/j.tcs.2012.12.030.

Full text

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!