Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world problems as objective functions and constraints are only ``approximately'' formulated for original real-world problems. To solve this issue, finding \emph{multiple} solutions is a natural direction, and diversity of solutions is an important concept in this context. Unfortunately, finding diverse solutions is much harder than finding a single solution. To cope with the difficulty, we investigate the approximability of finding diverse solutions. As a main result, we propose a framework to design approximation algorithms for finding diverse solutions, which yields several outcomes including constant-factor approximation algorithms for finding diverse matchings in graphs and diverse common bases in two matroids and PTASes for finding diverse minimum cuts and interval schedulings.

Abstract Given a graph $$G = (V,E)$$ G = ( V , E ) , $$A \subseteq V$$ A ⊆ V , and integers k and $$\ell $$ ℓ , the $$(A,\ell )$$ ( A , ℓ ) -Path Packing problem asks to find k vertex-disjoint paths of length exactly $$\ell $$ ℓ that have endpoints in A and internal points in $$V{\setminus }A$$ V \ A . We study the parameterized complexity of this problem with parameters |A|, $$\ell $$ ℓ , k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when $$\ell \le 3$$ ℓ ≤ 3 , while it is NP-complete for constant $$\ell \ge 4$$ ℓ ≥ 4 . We also show that the problem is W[1]-hard parameterized by pathwidth $${}+|A|$$ + | A | , while it is fixed-parameter tractable parameterized by treewidth $${}+\ell $$ + ℓ . Additionally, we study a variant called Short A-Path Packing that asks to find k vertex-disjoint paths of length at most $$\ell $$ ℓ . We show that all our positive results on the exact-length version can be translated to this version and show the hardness of the cases where |A| or $$\ell $$ ℓ is a constant.

Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in \(O\left (n \log n\right )\) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For \(\sqrt {n} \le s \le n\) , we present algorithms that use \(O\left (s \log n\right )\) bits and \(O\left (\frac {1}{s} \cdot n^{2} \cdot \log n\right )\) time for computing the length of a longest increasing subsequence, and \(O\left (\frac {1}{s} \cdot n^{2} \cdot \log ^{2} n\right )\) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.