Skip to content

Latest commit

 

History

History
1017 lines (829 loc) · 37.2 KB

problems.md

File metadata and controls

1017 lines (829 loc) · 37.2 KB
Raw

Problems

-- uncategorized

Frequent itemset mining

  • also called: 'FIM'
  • domain: 'Data analysis', 'Data mining'
  • paper: 'Mining association rules between sets of items in large databases' (1993) https://doi.org/10.1145/170035.170072
  • applications: 'Market basket analysis'

Multiset permutation

  • also called: 'Distinct permutation', 'Permutation with replacement'
  • https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets
  • solved by (libraries): 'sympy.utilities.iterables.multiset_permutations', 'more_itertools.distinct_permutations'
  • solved by (algorithms): 'Takaoka's multiset permutations algorithm'
  • related: 'Multinomial theorem' (number of multiset permutations)

Content-based near-duplicate video detection

  • also called: 'NDVD'

Simplification of Mixed Boolean-Arithmetic expressions

  • also called: 'MBA simplification'
  • applications paper: 'Information Hiding in Software with Mixed Boolean-Arithmetic Transforms' (2007) https://doi.org/10.1007/978-3-540-77535-5_5
  • applications: 'data flow obfuscation', 'obfuscation'
  • approaches: 'term rewriting / pattern matching'
  • solved by (libraries): 'Python quarkslab/arybo'
  • domain: 'cryptography', 'computer algebra', 'bit-vector logic'
  • thesis: 'Obfuscation with Mixed Boolean-Arithmetic Expressions: Reconstruction, Analysis and Simplification Tools'

Secure multi-party computation

Secure two-party computation

Oblivious transfer

Private information retrieval

-- implicit formulation with clear solutions

Solution is given by constraints which must be fullfilled, an equation to be solved.

Robust PCA problem

Greatest common divisor

Linear assignment problem

  • also called: 'Assignment problem', 'Cost minimizing assignment problem'
  • special case of: 'Linear programming', 'Maximum weight matching'
  • solved by (libraries): 'google/or-tools'
  • review paper: 'Assignment problems: A golden anniversary survey' (2007)

Quadratic assignment problem

Linear bottleneck assignment problem

Categorized assignment problem

Imbalanced time minimizing assignment problem

  • also called: 'ITMAP'
  • variant of: 'Linear bottleneck assignment problem', 'Categorized assignment problem'
  • original paper: 'A variant of time minimizing assignment problem' (1998)
  • paper: 'Exact Algorithms for the Imbalanced Time Minimizing Assignment Problem' (2001)
  • review paper: 'Assignment problems: A golden anniversary survey' (2007)
  • almost same problem: 'Agent Bottleneck Generalized Assignment Problem'
  • each machine must do at least one job
  • special case of: 'Mixed integer linear programming'

Agent Bottleneck Generalized Assignment Problem

  • also called: 'ABGAP'
  • original paper: 'Bottleneck generalized assignment problems' (1988)
  • paper: 'The multi-resource agent bottleneck generalised assignment problem' (2010)
  • almost same problem: 'Imbalanced time minimizing assignment problem'
  • no constraints on how many jobs per machine
  • special case of: 'Mixed integer linear programming'

Quadratic bottleneck assignment problem

Generalized assignment problem

  • also called: 'One-to-many assignment problem'

Many-to-many assignment problem

  • solved by (algorithm): 'Kuhn–Munkres algorithm with backtracking'

Bandwidth reduction problem

Matrix inversion

System of linear equations

Transportation problem

  • also called: 'Monge–Kantorovich transportation problem', 'Hitchcock–Koopmans transportation problem'
  • https://rosettacode.org/wiki/Transportation_problem
  • special case of: 'Linear programming', 'Minimum-cost flow problem'
  • commonly used heuristics: 'Northwest Corner Method'
  • solved by (algorithms): 'Network simplex algorithm'

Job shop scheduling

Degree diameter problem

Maximum flow problem

Minimum-cost flow problem

Finding spanning arborescence of minimum weight

  • also called: 'Minimum spanning arborescence', 'optimum branching problem'
  • input: 'Directed graph'
  • related adt: 'Spanning arborescence of minimum weight'
  • solved by (algorithm): 'Edmonds' algorithm'

Minimum-cost maximum-flow problem

  • variation of: 'Minimum-cost flow problem'

Minimum-cost circulation problem

0-1 knapsack problem

Graph matching problem

Graph isomorphism

Graph automorphism problem

Graph classification

-- explicit formulation with clear solutions

Solution is given by mathematical formula or naive computation method.

Hamming weight

Discrete Shearlet Transform

  • also called: 'DST'
  • paper: 'The Discrete Shearlet Transform: A New Directional Transform and Compactly Supported Shearlet Frames (2010)'
  • applications: 'Image processing', 'Facial Expression Recognition'
  • variant: 'Discrete Separable Shearlet Transform'

Mellin transform

Fourier transform

  • https://en.wikipedia.org/wiki/Fourier_transform
  • is a: 'Integral transform'
  • discrete version: 'Discrete Fourier transform'
  • applications: 'Signal processing', 'Analysis of differential equations', 'Quantum mechanics'
  • domain: 'Complex analysis'
  • input: function
  • output: function

Discrete Fourier transform

Discrete wavelet transform

Discrete cosine transform

Normalized cross-correlation

Image moments

Matrix chain multiplication

-- implicit or explicit formulation with clear solutions

Pareto frontier extraction

Disjoint set union problem

Watershed transformation

Connected-component finding ?rename, doesn't sound good'

Strongly connected component finding

Connected-component labeling

Minimum bounding box

  • https://en.wikipedia.org/wiki/Minimum_bounding_box
  • domain: 'Computational geometry'
  • solved by: 'Freeman-Shapira's minimum bounding box' (for convex polygons)
  • solved by?: 'Convex Hull' -> 'Freeman-Shapira's minimum bounding box' (for any set of points)
  • solved by?: 'Rotating calipers'

Line segment intersection

Synchronizing word

Road coloring problem

Travelling salesman problem

Vertex cover problem

Vertex cover decision problem

  • https://en.wikipedia.org/wiki/Vertex_cover
  • solved approximately by: 'Approximate global optimization'
  • hardness: 'NP-complete'
  • runtime complexity: polynomial for 'Bipartite Graph', 'Tree Graph'
  • is a: 'Decision problem'
  • kind of: 'Independent set problem'

Exact cover problem

Exact cover decision problem

Graph coloring problem (chromatic number)

Graph coloring problem (k-coloring)

Closest pair of points problem

Count-distinct problem

Single-source shortest path problem

  • also called: 'SSSP problem', 'Least cost path'
  • problem type: 'Shortest path problem'
  • https://en.wikipedia.org/wiki/Shortest_path_problem
  • book: 'Introduction to Algorithms'
  • survey paper: 'A Survey of Shortest-Path Algorithms' (2017)
  • find shortest path in graph so that the sum of edge weights is minimized
  • is a: 'optimization problem'
  • solved by 'Breadth-first search' for unweighted graphs
  • solved by 'Dijkstra's algorithm' for directed/undirected graphs and positive weights
  • solved by 'Bellman–Ford algorithm' for directed graphs with arbitrary weights
  • book: 'Introduction to Algorithms'
  • properties: 'optimal substructure'
  • domain: 'Graph theory'

Single-destination shortest path problem

k shortest path routing

Single-pair shortest path problem

All-pairs shortest paths problem

Longest path problem

  • also called: 'Longest simple path problem'
  • https://en.wikipedia.org/wiki/Longest_path_problem
  • hardness: NP-Hard
  • decision problem hardness: NP-complete
  • linear for Directed acyclic graph inputs (using topological sort)
  • In weighted complete graphs with non-negative edge weights, the weighted longest path problem is the same as 'Travelling salesman problem'

All-pairs shortest simple paths problem

  • related: 'All-pairs shortest paths problem'
  • allows negative cost cycles
  • NP-Hard

Graph connectivity

Negative cycle detection

Longest common substring problem

Longest palindromic substring problem

Longest common subsequence problem

  • also called: 'LCS', 'LCSS'
  • https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
  • book: 'Introduction to Algorithms', 'The Algorithm Design Manual'
  • cf. 'Longest common substring problem'
  • solved by: 'Hunt–McIlroy algorithm'
  • solved by application: 'diff'
  • applications: 'Version control systems', 'Wiki engines', 'Molecular phylogenetics'
  • domain: 'Combinatorics'

Shortest common supersequence problem

Shortest common superstring problem

Hamiltonian path problem

Maximum subarray problem

Eulerian path problem

  • https://en.wikipedia.org/wiki/Eulerian_path
  • application: 'in bioinformatics to reconstruct the DNA sequence from its fragments'
  • application: 'CMOS circuit design to find an optimal logic gate ordering'
  • compare: 'Hamiltonian path problem'
  • if exists, optimal solution for: 'Route inspection problem'
  • domain: 'Graph theory'
  • solved by (libraries): 'google/or-tools'

Route inspection problem

Closure problem

Point location problem

Point-in-polygon problem

Halfspace intersection problem

Largest empty sphere problem

Subset sum problem

Graph realization problem

Independent set decision problem

Finding a maximal independent set

Finding all maximal independent sets

Maximum independent set problem

Finding a maximum clique

Finding a maximum weight clique

Finding all maximal cliques

Clique decision problem

Edge dominating set decision problem

  • hardness: 'NP-complete'
  • is a: 'Decision problem'

Edge dominating set

Minimum edge dominating set

Set cover decision problem

Set cover problem

Weighted set cover problem

Maximal matching

Maximum matching

Minimum maximal matching

Boolean satisfiability problem

Nurse scheduling problem

Stable marriage problem

Partition problem

Linear partition problem

Maximum cut problem

Normalized Cut

Spanning-tree verification

  • book: 'Introduction to Algorithms'
  • related to: 'Minimum spanning tree'

Cycle decomposition

Envy-free item assignment

RSA problem

Integer factorization

DFA minimization

Topological sorting

  • https://en.wikipedia.org/wiki/Topological_sorting
  • book: 'The Algorithm Design Manual'
  • implemented by: 'posix tsort'
  • implemented in: 'boost::graph::topological_sort'
  • input: 'directed acyclic graph'
  • solved by: 'Depth-first search"
  • domain: 'Graph theory'

Polynomial factorization

Nearest neighbor search

Approximate nearest neighbor search

Range searching

Range reporting

Range counting

  • special case of: 'Range searching'
  • query name: 'Counting query'
  • answer type: int

Emptiness query of range searching

  • special case of: 'Range searching'
  • query name: 'Emptiness query'
  • answer type: bool

Lowest common ancestor

Longest common prefix problem

Range minimum query

Kernel density estimation

Sorting problem

Selection problem

Partial sorting

Incremental sorting

List ranking

Shortest pair of edge disjoint paths

  • special case of: 'Minimum-cost flow problem'
  • applications: 'Routing'
  • domain: 'Graph theory'

Minimal Perfect Hashing

K-server problem

X + Y sorting

3SUM

Motion planning

Covariance matrix estimation

-- problems with clear solutions for simple metrics (multiple metrics possible)

Downsampling

Biclustering

Sequence alignment

Template matching

Hierarchical clustering

Approximate string matching

-- problems with approximate solutions only (no known way to have 100% perfect results)

Evaluation is usually empirical, based on metrics inpired by human perception or compared to groundtruth based on some metric.

Audio time stretching and pitch scaling

Optical flow

Video denoising

Music source separation

Image segmentation

Superpixel

Image binarization

Stemming

Part-of-speech tagging

Multivariate interpolation

  • also called: 'Spatial interpolation'

Image scaling

Single image super-resolution

  • also called: 'SISR'

Pixel-art scaling

Demosaicing

Blind deconvolution

Direction finding

  • also called: 'DF', Radio direction finding', 'RDF'

Frequency estimation

Grammatical error correction

Speech recognition

Speaker recognition

Handwriting recognition

  • also called: 'HWR', 'Handwritten Text Recognition', 'HTR'
  • https://en.wikipedia.org/wiki/Handwriting_recognition
  • input: 'image' (offline) or f(time) -> (real, real, bool) (online)
  • output: '(formatted) text'
  • conferences: 'International Conference on Frontiers in Handwriting Recognition'

-- subjective (no simple objective performance metric)

Empirical evaluation or based on "dumb" metrics. Even comparison to groundtruth is not easily possible.

Image registration

Inpainting

Image tracing

  • also called: 'raster-to-vector conversion', 'vectorization'
  • domain: 'computer graphics'
  • related problems: 'Image scaling'
  • applications: 'Potrace', 'CorelDRAW PowerTRACE'

Terrain generation

Image retargeting

  • also called: 'content-aware image resizing'
  • review paper: 'A Comparative Study of Image Retargeting' (2010)
  • solved by (selection): 'Seam carving'
  • domain: 'Image processing', 'Computer graphics'

Paraphrase generation

  • metrics (selection): 'BLEU'
  • usually solved by: 'machine learning'

Machine translation

  • also called: 'MT'
  • https://en.wikipedia.org/wiki/Machine_translation
  • domain: 'Computational linguistics'
  • metrics (selection): 'BLEU', 'ROUGE'
  • usually solved by: 'machine learning'
  • approaches: 'Statistical machine translation', 'Neural machine translation', 'Rule-based machine translation', 'Dictionary-based machine translation'