Polynomial-Time Algorithm for Learning Optimal BFS-Consistent Dynamic Bayesian Networks [PDF]
Entropy, 2018 Dynamic Bayesian networks (DBN) are powerful probabilistic representations that model stochastic processes. They consist of a prior network, representing the distribution over the initial variables, and a set of transition networks, representing the ...
Margarida Sousa, Alexandra M. Carvalho
doaj +2 more sources
A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits
Physical Review XWe provide a polynomial-time classical algorithm for noisy quantum circuits. The algorithm computes the expectation value of any observable for any circuit, with a small average error over input states drawn from an ensemble (e.g., the computational ...
Thomas Schuster +3 more
doaj +2 more sources
A polynomial-time algorithm for sailing speed optimization with containership resource sharing
Transportation Research Part B: Methodological, 2016 The sailing speed optimization problem aims to determine the optimal cruising speeds of ships by balancing the number of ships required on services, the fuel consumption, and the level of service provided for customers.
Shuai-An Wang, Xin-Chang Wang
semanticscholar +3 more sources
Propose a Polynomial Time Algorithm for Total Completion Time Objective [PDF]
International Journal of Mathematical, Engineering and Management Sciences, 2021 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.
Yucel Ozturkoglu, Omer Ozturkoglu
doaj +1 more source
A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games [PDF]
Embedded Systems and Applications, 2022 Since the celebrated PPAD-completeness result for Nash equilibria in bimatrix games, a long line of research has focused on polynomial-time algorithms that compute ε-approximate Nash equilibria.
Argyrios Deligkas +2 more
semanticscholar +1 more source
A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling [PDF]
Symposium on the Theory of Computing, 2022 We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance.
D. Aharonov +4 more
semanticscholar +1 more source
A Polynomial Time Algorithm for the k-Disjoint Shortest Paths Problem
ACM-SIAM Symposium on Discrete Algorithms, 2021 The disjoint paths problem is a fundamental problem in algorithmic graph theory and combinatorial optimization. For a given graph G and a set of k pairs of terminals in G , it asks for the existence of k vertex-disjoint paths connecting each pair of ...
William Lochet
semanticscholar +1 more source
Learning Quantum Hamiltonians at Any Temperature in Polynomial Time [PDF]
Symposium on the Theory of Computing, 2023 We study the problem of learning a local quantum Hamiltonian H given copies of its Gibbs state ρ = e−β H/(e−β H) at a known inverse temperature β>0. Anshu, Arunachalam, Kuwahara, and Soleimanifar gave an algorithm to learn a Hamiltonian on n qubits to ...
Ainesh Bakshi +3 more
semanticscholar +1 more source
An expected polynomial time algorithm for coloring 2-colorable 3-graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2011 Graphs and ...
Yury Person, Mathias Schacht
doaj +1 more source
A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation [PDF]
Operations Research Letters, 2019 We consider fair allocation of indivisible items under additive utilities. When the utilities can be negative, the existence and complexity of an allocation that satisfies Pareto optimality and proportionality up to one item (PROP1) is an open problem ...
H. Aziz, H. Moulin, Fedor Sandomirskiy
semanticscholar +1 more source