# Questions tagged [combinatorial-optimization]

Combinatorial optimization typically deals with optimizing over a finite set of objects that have some combinatorial structure (e.g. trees, matchings, matroids). Approximation algorithms, polyhedral methods, and integer programming are all on topic.

**1**

**1**answer

### Is this variant of knapsack problem strongly NP-hard?

**2**

**1**answer

### Minimizing the degree of outgoing edges in a digraph, does this problem have a name?

**0**

**0**answers

### k-secretary problem: not knowing the length of the queue

**4**

**2**answers

### High degree differences in bipartite graphs

**1**

**1**answer

### Knapsack problem with capacity constraint

**15**

**2**answers

### n sets, each is large, the intersection of every three is small, what is the size of the union?

**4**

**0**answers

### Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$

**1**

**1**answer

### Knapsack problem with value range constraint

**0**

**0**answers

### Probability that edge exchange yields a tour

**1**

**0**answers

### Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph

**0**

**1**answer

### What's the meaning of this in equality in the lot-sizing and scheduling problem

**0**

**0**answers

### Bounds on the lengths of circuits in a metric space

**9**

**3**answers

### Pairs of vertices with high degree difference

**1**

**1**answer

### $\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves

**1**

**1**answer

### Column subset selection with least angle optimization

**0**

**1**answer

### What is the computational complexity of the calculation of $ \Psi(x) $?

**2**

**0**answers

### Maximum number of regions in a disk partitioned by pairs of parallel chords

**1**

**1**answer

### Relation of 1-trees to optimal tours

**1**

**0**answers

### Monotone rearrangements of function, constrained optimization in $\mathcal{L}^p$

**3**

**0**answers

### Matrix inequality $a X \succeq arcsin(X)$ for some $a > 0$

**1**

**0**answers

### Term or reference for a set of integer edge weights to guarantee distinct weighted degrees

**0**

**1**answer

### A question on graph partitioning

**0**

**0**answers

### Examples of recursive TSP heuristics

**0**

**0**answers

### Complexity of heaviest 2-optimal vertex-disjoint cycle covers

**1**

**0**answers

### Optimality of trees generated via edge exchanges

**0**

**0**answers

### How to prevent spanning trees from spiraling

**0**

**0**answers

### Optimality of a heuristic for conflict resolution

**1**

**0**answers

### Generating triangulations with given topology

**3**

**0**answers

### Additional symmetries of the Traveling Salesman Polytope

**0**

**1**answer

### Maximize sum of edge weights on spanning tree

**0**

**0**answers

### Identifying essential degree constraints for ILP formulations of combinatorial optimal graph problems

**0**

**1**answer

### maximum number of colors for an optimal tiling which guaranties infinite paths

**1**

**1**answer

### Complexity of calculating the optimal amalgamation of an optimal cycle-cover

**1**

**0**answers

### Relationship between Wasserstein projections and metric projections in a linear space

**2**

**1**answer

### Combinatorial process on multisets of integers

**2**

**0**answers

### What is the optimal upper bound of $|T_1|+|T_2|+|T_3|$ if $T_1, T_2, T_3$ are trees covering a planar graph

**7**

**1**answer

### Vectors with minimal Hamming weight in a rational vector space?

**3**

**1**answer

### Combinatorial Euclidean geometry problem

**0**

**0**answers

### Is there one 1.5 approximate algorithm to solve edge-fixed TSP and TSP path?

**2**

**0**answers

### Minimizing a certain norm of the identity operator on $\mathbb R^2$

**5**

**1**answer

### On a certain norm of the identity operator on $\mathbb R^2$

**1**

**0**answers

### Barycentric coordinates of weighted edges

**1**

**0**answers

### Methods for useful visualisations of complete weighted graphs

**0**

**0**answers

### How to define optimal substructure in graph search problems if the edges are functions instead of weights?

**0**

**0**answers

### Hardness of finding optimal tours in Hamiltonian Apollonian gaskets

**1**

**0**answers

### Calculating vertex weights via mutually tangent circles of triangles

**6**

**1**answer

### Subsets of a ball/sphere with the largest sum of distances

**1**

**0**answers

### The earliest discrete optimization problem

**6**

**2**answers

### Snake algorithm that minimizes straight lines

**0**

**0**answers