Search · four archives
Search · four archives
14 papers · ranked by Valyu relevance
Max A. Little, Xi He, Ugur Kayas
Dynamic programming (DP) is a broadly applicable algorithmic design paradigm for the efficient, exact solution of otherwise intractable, combinatorial problems. However, the design of such algorithms is often presented informally in an ad-hoc manner, and as a result is often difficult to apply correctly. In this paper…
Nicklas Hoch, Ugo Montanari, Matteo Sammartino
Many optimization problems can be naturally represented as (hyper) graphs, where vertices correspond to variables and edges to tasks, whose cost depends on the values of the adjacent variables. Capitalizing on the structure of the graph, suitable dynamic programming strategies can select certain orders of evaluation of…
Ryo Kuroiwa, J. Christopher Beck
- We propose domain-independent dynamic programming (DIDP), a novel model-based paradigm for combinatorial optimization. - The modeling language for DIDP is designed so that a user can investigate efficient models by incorporating redundant information. - We implement DIDP solvers using heuristic search in an…
Jesse Hoey, Robert St‐Aubin, Alan J. Hu, Craig Boutilier
Recently, structured methods for solving factored Markov decisions processes (MDPs) with large state spaces have been proposed recently to allow dynamic programming to be applied without the need for complete state enumeration. We propose and examine a new value iteration algorithm for MDPs that uses algebraic decision…
Martin Fürer, Huiwen Yu
Dynamic programming is widely used for exact computations based on tree decompositions of graphs. However, the space complexity is usually exponential in the treewidth. We study the problem of designing efficient dynamic programming algorithm based on tree decompositions in polynomial space. We show how to construct a…
Scott Sanner, Karina Valdivia Delgado, Leliane Nunes de Barros
Many real-world decision-theoretic planning problems can be naturally modeled with discrete and continuous state Markov decision processes (DC-MDPs). While previous work has addressed automated decision-theoretic planning for DC-MDPs, optimal solutions have only been defined so far for limited settings, e.g., DC-MDPs…
Thomas J. Sargent, John Stachurski
We introduce a framework that represents dynamic programs as families of policy operators acting on a partially ordered set. We provide an optimality theory based on high-level assumptions and show how applications across a broad spectrum of dynamic programming subfields fit into this framework. We apply the framework…
Zedong Peng, Albert Lee, David E. Bernal Neira
Discrete-Steepest Descent Algorithm Authors: ['Zedong Peng' 'Albert Lee' 'David E. Bernal Neira'] Abstract— Dynamic optimization problems involving discrete decisions have several applications, yet lead to challenging optimization problems that must be addressed efficiently. Combining discrete variables with…
Thomas J. Sargent, John Stachurski
| Preface | | | viii | | --- | --- | --- | --- | | Common Symbols | | | xi | | | Common Abbreviations | | xii | | 1 | Introduction | | 1 | | | 1.1 Bellman Equations | | 3 | | | 1.1.1 | Finite-Horizon Job Search | 3 | | | 1.1.2 Infinite Horizon | | 10 | | | 1.2 Stability and Contractions | | 12 | | | 1.2.1 Vector Space…
Frederik Gossen, Marc Jasper, Alnis Murtovi, Bernhard Steffen
In this paper, we propose a new paradigm for program optimization which is based on aggressive aggregation, i.e., on a partial evaluation-based decomposition of acyclic program fragments into a pair of computationally optimal structures: an Algebraic Decision Diagram (ADD) to capture conditional branching and a…
Carola Doerr, Anton V. Eremeev, Christian Horoba, Frank Neumann + 1 more
'Madeleine Theile'] Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation which enables them to construct solutions in a dynamic programming…
Tim Vieira, Ryan Cotterell, Jason Eisner
Computational models of human language often involve combinatorial problems. For instance, a probabilistic parser may marginalize over exponentially many trees to make predictions. Algorithms for such problems often employ dynamic programming and are not always unique. Finding one with optimal asymptotic runtime can be…
Andrej Bauer, Matija Pretnar
Eff is a programming language based on the algebraic approach to computational effects, in which effects are viewed as algebraic operations and effect handlers as homomorphisms from free algebras. Eff supports first-class effects and handlers through which we may easily define new computational effects, seamlessly…
L. Mandow, José-Luís Pérez-de-la-Cruz, N. Pozas
This paper addresses the problem of approximating the set of all solutions for Multi-objective Markov Decision Processes. We show that in the vast majority of interesting cases, the number of solutions is exponential or even infinite. In order to overcome this difficulty we propose to approximate the set of all…