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…
Pedro Afonso Fernandes
Economic forecasting is concerned with the estimation of some variable like gross domestic product (GDP) in the next period given a set of variables that describes the current situation or state of the economy, including industrial production, retail trade turnover or economic confidence. Neuro-dynamic programming…
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, Edward Lam
Authors are encouraged to submit new papers to INFORMS journals by means of a style file template, which includes the journal title. However, use of a template does not certify that the paper has been accepted for publication in the named journal. INFORMS journal templates are for the exclusive purpose of submitting to…
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…
Keehang Kwon
Inspired by computability logic[1], we refine recursive function definitions into two kinds: blindly-quantified (BQ) ones and parallel universally quantified (PUQ) ones. BQ definitions corresponds to the traditional ones where recursive definitions are not evolving. PUQ definitions are evolving in the course of…
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).…
Michael Emmerich
Dynamic Programming Authors: ['Michael Emmerich'] We present a dynamic programming algorithm for selecting a representative subset of size k from a given set with n points such that the Riesz s-energy is near minimized. While NP-hard in general dimensions, the one-dimensional case can use the natural data ordering for…
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…
Sepideh Aghamolaei, Mohammad Ghodsi
The rectangle escape problem (REP) is defined as follows: For n axisaligned rectangles inside an axis-aligned bounding box B, extend each rectangle in only one of the four directions: up, down, left, or right until it reaches B and the density k is minimized, where k is the maximum number of extensions of rectangles to…
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…
Chuyu Xiong
Computational complexity is a core theory of computer science, which dictates the degree of difficulty of computation. There are many problems with high complexity that we have to deal, which is especially true for AI. This raises a big question: Is there a better way to deal with these highly complex problems other…