| 1 |
Front Matter |
|
|
Abstract
|
| 2 |
,Introduction, |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
The dynamic programming has been studied intensively from its development by Richard Bellman in the 1950s [.] and applied to multiple domains such as control theory, economics, or in general, to optimization field. In this book, we consider dynamic programming in the realm of multi-objective (multi-criteria) combinatorial optimization. Our proposed algorithmic framework tackles two multi-objective optimization approaches, a priori and a posteriori optimization methods. In the a priori method, a combinatorial optimization problem is sequentially optimized with respect to several objectives ordered according to their significance. We refer to this approach as multi-stage optimization. It can be considered as a special case of lexicographic optimization. Contrarily, the a posteriori method provides an opportunity to revoke an order of objectives resulting in simultaneous optimization relative to two criteria. The aim is to find the set of Pareto optimal points related to the Pareto optimal solutions, which cannot be improved without worsening at least one objective. We refer to this approach as bi-criteria optimization.
|
| 3 |
|
|
|
Abstract
|
| 4 |
Circuits and Cost Functions |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
In this chapter, we consider the notion of a circuit and the notion of a cost function for this circuit. The circuit builds a set of elements for the optimization (a set of feasible solutions) from one-element sets attached to input nodes using the operation of union of sets attached to unifying nodes and functional operations attached to functional nodes. The cost function corresponds a real number (a cost) to each element. Our goal is to minimize the cost.
|
| 5 |
Multi-Stage Optimization and Counting Optimal Elements |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
In this chapter, we propose an optimization procedure (an algorithm .), which for a given circuit without repetitions and cost function for this circuit, transforms the circuit into its subcircuit. For strictly increasing cost functions, the set of elements described by the subcircuit coincides with the set of optimal elements relative to the considered cost function. For increasing cost functions, the set of elements described by the subcircuit is a nonempty subset of the set of optimal elements.
|
| 6 |
Bi-Criteria Optimization of Elements |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
In this chapter, we take special attention to bi-criteria optimization problems relative to two increasing cost functions, and propose an algorithm . for the construction of the set of Pareto optimal points for such a problem.
|
| 7 |
|
|
|
Abstract
|
| 8 |
Matrix Chain Multiplication |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
Matrix chain multiplication is one of the classic optimization problems in computer science. For a given sequence ., . of matrices, we need to compute the product of these matrices using the minimum number of scalar multiplications on a single processor machine.
|
| 9 |
Global Sequence Alignment |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
The sequence alignment problem is a generalization of the edit distance problem (see Levenshtein [.]), which measures the difference between two sequences by the minimum number of removals, insertions, and substitutions of symbols required to obtain one sequence from the another. The solution to the sequence alignment problem helps to identify biological similarities in long sequences of DNA, RNA, and proteins.
|
| 10 |
Optimal Paths in Directed Graphs |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
The problem of path length minimization in graphs is very well known. There are algorithms solving this problem based on a greedy approach such as Dijkstra’s algorithm [.], algorithms based on a dynamic programming approach such as Floyd-Warshall algorithm [., .], etc.
|
| 11 |
Binary Search Trees |
|
|
Abstract
|
| 12 |
Convex Polygon Triangulation |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
A convex polygon triangulation is a decomposition of the polygon into a set of triangles with pairwise non-intersecting interiors whose union is this polygon.
|
| 13 |
Line Breaking |
|
|
Abstract
|
| 14 |
One-Dimensional Clustering |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
The clustering is a task of grouping objects, which are similar with respect to some metric. Clustering is a well-known problem in statistics, data mining, and machine learning.
|
| 15 |
Optimal Bitonic Tour |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
The optimal bitonic tour problem is a restricted variant of the Euclidean traveling salesman problem introduced by J. L. Bentley. This problem can be solved by a dynamic programming algorithm in polynomial time [.].
|
| 16 |
Segmented Least Squares |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
The least squares method is widely used in statistics with common application to regression. The aim is to fit a linear function to set of points that minimizes the sum of the squares of the residuals. In some cases, fitting a linear function with a relatively small error is impossible. Keeping the linear character of approximation, the data points can be split into a sequence of segments, where to each of the segments the line given by a linear function is fitted. The optimization objectives for this problem is to minimize the total least squares error for all segments and to minimize the number of segments used. We refer to such a problem as segmented least squares.
|
| 17 |
|
|
|
Abstract
|
| 18 |
Discussion of Matching Optimization Problem and Representation of Matchings |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
In this chapter, we discuss the problem of optimization of matchings in trees including its relation to the kidney paired donation. We did not find a conventional circuit without repetitions that represents the set of all matchings for an arbitrary tree. Instead of a circuit, we construct a labeled forest to describe the set of matchings [.]. We use this forest in multi-stage and bi-criteria optimization and counting matchings.
|
| 19 |
Counting Matchings and Multi-Stage Optimization of Matchings |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
In this chapter, we consider the algorithm . for counting matchings and the algorithm . for optimization of matchings relative to a weight function. The algorithm of optimization . can be used for multi-stage optimization of matchings relative to a sequence of weight functions, and the algorithm . can be used for counting the optimal matchings after each step of optimization. This chapter contains some revised results from the conference paper [.].
|
| 20 |
Bi-Criteria Optimization of Matchings |
Michal Mankowski,Mikhail Moshkov |
|
Abstract
In this chapter, we describe an additional tool for the study of Pareto optimal points (POPs) in comparison to ones considered in Sect. .: the algorithm . for the fusion of sets of POPs [.]. We also propose the algorithm ., which constructs the set of POPs for bi-criteria optimization of matchings in trees relative to two weight functions. In the end of the chapter, we discuss the notion of a totally optimal matching (optimal relative to two weight functions simultaneously) and show how we can recognize the existence of totally optimal matchings using multi-stage and bi-criteria optimization algorithms. This chapter contains some revised results from the conference paper [.].
|
发表于 2025-3-21 19:24:11
