15 papers · ranked by Valyu relevance
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…
David H. Lee, Aditya Prasad, Ramiro Deo-Campo Vuong, Tianyu Wang + 2 more
'Eric Han' 'David Kempe'] Dynamic programming (DP) is a fundamental and powerful algorithmic paradigm taught in most undergraduate (and many graduate) algorithms classes. DP problems are challenging for many computer science students because they require identifying unique problem structures and a refined understanding…
Ryo Kuroiwa, J. Christopher Beck
For combinatorial optimization problems, model-based approaches such as mixed-integer programming (MIP) and constraint programming (CP) aim to decouple modeling and solving a problem: the 'holy grail' of declarative problem solving. We propose domain-independent dynamic programming (DIDP), a new model-based paradigm…
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…
Monika Henzinger, Stefan Neumann, Harald Räcke, Stefan Schmid
Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases…
van Melkebeek, Dieter
We show for several computational problems how classical greedy algorithms for special cases can be derived in a simple way from dynamic programs for the general case: interval scheduling (restricted to unit weights), knapsack (restricted to unit values), and shortest paths (restricted to nonnegative edge lengths).…
Andrew Conway
For those new to the field, this paper is designed to be an introduction to many of the tricks for producing efficient enumeration algorithms. For those more experienced, it will hopefully help them understand the interrelationship and implications of a variety of techniques, many or most of which will be familiar. The…
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…
Anurag Dutta, K. Lakshmanan, John Harshith, Aditya Ramamoorthy
Problem: The Maximal Stretch Authors: ['Anurag Dutta' 'K. Lakshmanan' 'John Harshith' 'Aditya Ramamoorthy'] Abstract. Mathematical Selection is a method in which we select a particular choice from a set of such. It have always been an interesting field of study for mathematicians. Combinatorial optimisation is the…
Eugene Callahan, Robert A. Murphy, Anas Elghafari
Students of Computer Science often wonder when, exactly, one can apply a greedy algorithm to a problem, and when one must use the more complicated and time-consuming techniques of dynamic programming. This paper argues that the existing pedagogical literature does not offer clear guidance on this issue. We suggest…
Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier + 1 more
'Thomas Zeume'] Abstract. Which amount of parallel resources is needed for updating a query result after changing an input? In this work we study the amount of work required for dynamically answering membership and range queries for formal languages in parallel constant time with polynomially many processors. As a…
Chee-Khian Sim
polynomial complexity Authors: ['Chee-Khian Sim'] In this note, we polynomially reduce an instance of the partition problem to a dynamic lot sizing problem, and show that solving the latter problem solves the former problem. By solving the dynamic programming formulation of the dynamic lot sizing problem, we show that…
Leonardo Cano, Yewen Pu, Robert D. Hawkins, Josh Tenenbaum + 1 more
'Armando Solar-Lezama'] A typical way in which a machine acquires knowledge from humans is by programming. Compared to learning from demonstrations or experiences, programmatic learning allows the machine to acquire a novel skill as soon as the program is written, and, by building a library of programs, a machine can…
Ragav Sachdeva, Frank Neumann, Markus Wagner
Many real-world optimisation problems involve dynamic and stochastic components. While problems with multiple interacting components are omnipresent in inherently dynamic domains like supply-chain optimisation and logistics, most research on dynamic problems focuses on single-component problems. With this article, we…