Combinatorial Optimization & Game Problems

← Back to Domain-Specific Families

Abstractions about optimizing or analyzing discrete combinatorial and game-theoretic problems — partitioning and covering problems (partition problem, quadratic knapsack, matroid-constrained partitioning, Steiner system), location and scheduling problems (1-center problem, maximum subarray), and game-theoretic models such as graphical game theory and Silverman's game.

12 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.

• 1-Center Problem — A minimax location problem that places one center to minimize the largest distance or service cost to any demand point.
• Domination Analysis — Domination analysis evaluates a heuristic by the number of feasible solutions its output is guaranteed to match or beat, rather than only by its gap from the optimum.
• Etemadi's Inequality — A maximal inequality bounding excursions of independent partial sums by the worst partial-sum tail probability at a smaller threshold.
• Graphical Game Theory — A compact representation of a strategic game in which a graph records each player's local payoff dependencies, so a player's utility is specified only over its own action and those of its graph neighbors.
• Matroid-Constrained Number Partitioning — A multiway number-partitioning problem in which every assigned subset must be independent in a corresponding matroid, while a declared aggregate objective balances or optimizes the subsets' weights.
• Maximum subarray problem — The problem of finding a contiguous interval of a numeric array whose elements have the maximum possible sum.
• Parthasarathy's Theorem — A minimax theorem for bounded unit-square games with finitely many curve discontinuities, obtaining a mixed value when one player is restricted to Lebesgue-absolutely-continuous strategies.
• Partition problem — The problem of dividing a multiset of positive integers into two exhaustive parts with equal sums, or minimizing their sum difference.
• Quadratic knapsack problem — A capacity-constrained item-selection optimization with pairwise and optional individual profits.
• Silverman's game — A two-player zero-sum number-selection game that rewards a moderately larger choice but penalizes a choice whose ratio to the opponent's reaches a fixed threshold.
• Steiner system — An n-point uniform block design S(t,k,n) in which every t-point subset occurs in exactly one k-point block.
• Successor Ordinal — An ordinal of the form α+1: the least ordinal strictly greater than α, represented in the von Neumann model as α united with the singleton containing α.