Combinatorial Optimization

← Back to Domain-Specific Abstractions by Domain

10 domain-specific abstractions whose origin domain is Combinatorial Optimization.

• 3-dimensional matching — A matching in a tripartite 3-uniform hypergraph: a set of triples no two of which share any coordinate, with optimization and perfect-decision variants.
• Balanced matrix — A binary matrix containing no odd-order square submatrix in which every row and column has exactly two ones.
• Circulation problem — A network-flow feasibility or optimization problem assigning edge flows within lower and upper bounds while conserving flow at every vertex.
• Closure problem — The optimization problem of selecting a maximum-weight vertex set in a directed graph subject to the rule that selecting a vertex also selects every vertex reachable along its outgoing dependencies.
• Gomory–Hu tree — A weighted tree representing every pairwise minimum-cut value of an undirected capacitated graph through the minimum edge on the corresponding tree path.
• Matroid parity problem — The optimization problem of selecting the largest collection of prescribed element pairs whose union is independent in a matroid.
• Maximum satisfiability problem — The optimization problem of assigning Boolean variables to maximize the number or total weight of satisfied clauses in a conjunctive normal form formula.
• Quasi-bipartite graph — A Steiner-tree instance in which the nonterminal vertices form an independent set, so every edge has at least one terminal endpoint.
• Set TSP problem — A traveling-salesman generalization seeking a minimum-cost tour that visits at least one vertex from every specified group.
• Submodular flow — A combinatorial optimization problem that minimizes linear flow cost subject to edge bounds and submodular constraints on net flow across every vertex subset.