Combinatorial Optimization & Discrete Structures

← Back to Domain-Specific Families

Abstractions about discrete mathematical structures and combinatorial optimization problems, including graph and hypergraph properties (giant component, width of a hypergraph, D-interval hypergraph), geometric covering and packing problems (disk-covering problem, strip packing problem, smallest-circle problem), and algorithms or metrics for search and design (A-star algorithm, Fréchet distance, Plackett-Burman design).

31 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• A-star algorithm — A* (pronounced "A-star") is a graph traversal and pathfinding algorithm that is used in many fields of computer science due to its completeness, optimality, and optimal efficiency.
• Algebraic curve — A projective algebraic plane curve is the zero set in a projective plane of a homogeneous polynomial in three variables.
• Constrained Shortest Path First — Constrained Shortest Path First (CSPF) is an extension of shortest path algorithms.
• D-interval hypergraph — In graph theory, a -interval hypergraph is a kind of a hypergraph constructed using intervals of real lines.
• Davenport–Schinzel sequence — In combinatorics, a Davenport–Schinzel sequence is a sequence of symbols in which the number of times any two symbols may appear in alternation is limited.
• Disk-Covering Problem — One of the covering disks is placed central and the remaining five in a symmetrical way around it.
• Equidistribution Theorem — The theorem that successive multiples of an irrational number, reduced modulo one, become uniformly distributed on the unit interval or circle.
• Fréchet distance — In mathematics, the Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves.
• Giant Component — In network theory, a giant component is a connected component of a given random graph that contains a significant fraction of the entire graph's vertices.
• Greedy Randomized Adaptive Search Procedure — The greedy randomized adaptive search procedure (also known as GRASP) is a metaheuristic algorithm commonly applied to combinatorial optimization problems.
• Kendall tau distance — The Kendall tau distance or Kendall tau rank distance is a metric (distance function) that counts the number of pairwise disagreements between two ranking lists.
• Lattice Model (Physics) — In mathematical physics, a lattice model is a mathematical model of a physical system that is defined on a lattice, as opposed to a continuum, such as the continuum of space or spacetime.
• Lottery ticket hypothesis — In machine learning, the lottery ticket hypothesis is that artificial neural networks with random weights can contain a subnetwork which (entirely by chance) can be tuned to a similar performance as tuning the whole network.
• Metric k-center — In graph theory, the metric -center problem or vertex k-center problem is a classical combinatorial optimization problem studied in theoretical computer science that is NP-hard.
• Moving-Cluster Method — In astrometry, the moving-cluster method and the closely related convergent point method are means, primarily of historical interest, for determining the distance to star clusters.
• Multiplicative Cascade — In mathematics, a multiplicative cascade is a fractal/multifractal distribution of points produced via an iterative and multiplicative random process.
• Packing density — A packing density or packing fraction of a packing in some space is the fraction of the space filled by the figures making up the packing.
• Plackett–Burman Design — Plackett–Burman designs are experimental designs presented in 1946 by Robin L.
• Point counting (geology) — In geology, point counting is a method to determine the proportion of an area that is covered by some objects of interest.
• Pyjama problem — In mathematics, the pyjama problem asks whether the plane can be covered by a finite number of rotated copies of a repeating pattern of stripes ("pyjama stripes"), no matter how thin the stripes are.
• Reconfiguration — In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.
• Ring star problem — The ring star problem (RSP) is a NP-hard problem in combinatorial optimization.
• Rotation matrix — In linear algebra, a rotation matrix is a transformation matrix that is used to perform a rotation in Euclidean space.
• Skip list — In computer science, a skip list (or skiplist) is a probabilistic data structure that allows \mathcal O(\log n) average complexity for search as well as \mathcal O(\log n) average complexity for insertion within an ordered sequence of n elements.
• Smallest-Circle Problem — The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane.
• Squared Triangular Number — In number theory, the sum of the first cubes is the square of the th triangular number.
• Strip packing problem — The strip packing problem is a 2-dimensional geometric minimization problem.
• Tractable Problem — Tractable problems are frequently identified with problems that have polynomial-time solutions ( \textsf{P} , \textsf{PTIME} ); this is known as the Cobham–Edmonds thesis.
• Unimodality — Unimodality is the property of a distribution or other mathematical object having one mode or single highest region under a stated definition.
• Wang tile — Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, is a class of formal systems.
• Width of a hypergraph — In graph theory, there are two related properties of a hypergraph that are called its "width".