Thirty-seven research problems are described, covering a wide range of combinatorial topics. Unlike Hilbert''s problems, most of these are not especially famous and they might be "do-able" in the next few years. (Problems 1-16 were contributed by Klarner, 17-26 by Chvatal, 27-37 by Knuth. All cash awards are Chvatal''s responsibility.)
Cited By
- Ceglarek D, Haniewicz K and Rutkowski W Robust plagiary detection using semantic compression augmented SHAPD Proceedings of the 4th international conference on Computational Collective Intelligence: technologies and applications - Volume Part I, (308-317)
- Antoš J and Melichar B Finite automata for generalized approach to backward pattern matching Proceedings of the 15th international conference on Implementation and application of automata, (49-58)
- Yang I, Huang C and Chao K (2005). A fast algorithm for computing a longest common increasing subsequence, Information Processing Letters, 93:5, (249-253), Online publication date: 1-Mar-2005.
- Breimer E, Goldberg M and Lim D (2003). A learning algorithm for the longest common subsequence problem, ACM Journal of Experimental Algorithmics, 8, (2.1-es), Online publication date: 31-Dec-2004.
- Chen D, Daescu O, Hu X and Xu J (2003). Finding an optimal path without growing the tree, Journal of Algorithms, 49:1, (13-41), Online publication date: 1-Oct-2003.
- Amir A, Aumann Y, Landau G, Lewenstein M and Lewenstein N (2000). Pattern Matching with Swaps, Journal of Algorithms, 37:2, (247-266), Online publication date: 1-Nov-2000.
- Mukherjee A (1989). Hardware Algorithms for Determining Similarity Between two Strings, IEEE Transactions on Computers, 38:4, (600-603), Online publication date: 1-Apr-1989.
- Hsu W New algorithms for comparing symbol sequences Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, (381-389)
- Hunt J and Szymanski T (1977). A fast algorithm for computing longest common subsequences, Communications of the ACM, 20:5, (350-353), Online publication date: 1-May-1977.
- Ullman J, Aho A and Hirschberg D (1976). Bounds on the Complexity of the Longest Common Subsequence Problem, Journal of the ACM, 23:1, (1-12), Online publication date: 1-Jan-1976.
- Hirschberg D (1975). A linear space algorithm for computing maximal common subsequences, Communications of the ACM, 18:6, (341-343), Online publication date: 1-Jun-1975.
- Bitner J and Reingold E (1975). Backtrack programming techniques, Communications of the ACM, 18:11, (651-656), Online publication date: 1-Nov-1975.
Recommendations
Combinatorial Structure of Schulte's Chiral Polyhedra
Schulte classified the discrete chiral polyhedra in Euclidean 3-space and showed that they belong to six families. The polyhedra in three of the families have finite faces and the other three families consist of polyhedra with (infinite) helical faces. ...
Quantitative Combinatorial Geometry for Continuous Parameters
We prove variations of Carathéodory's, Helly's and Tverberg's theorems where the sets involved are measured according to continuous functions such as the volume or diameter. Among our results, we present continuous quantitative versions of Lovász's ...
On the convex hull of feasible solutions to certain combinatorial problems
By Weyl's Theorem, the convex hull of the set of (characteristic vectors of) feasible solutions to combinatorial problems is a convex polyhedron when there is a finite number of feasible solutions. This need not be the case of infinite solution sets, ...