# Questions tagged [discrete-optimization]

For questions about discrete optimization, which is a branch of optimization with discrete variables, opposed to continuous optimization in applied mathematics and computer science.

1,104 questions
Filter by
Sorted by
Tagged with
51 views

### Allocating one source to each islanded subgraph

Suppose $G$ is a graph. $E(G)$ and $V(G)$ denote the sets of the edges and nodes (vertices) of $G$, respectively. Below is shown a graph with 9 nodes and 12 edges, which I will use as an example. <...
65 views

### Minimum amount of required chits to award player points

There is a board game for up to four players that has 7 rounds and at the end of each round the game awards the first player 3 points, the second 2, the third 1 and the fourth 0 points. The points are ...
184 views

### Why does a 3-regular planar graph of diameter 3 have at most 12 vertices?

Today, I saw an interesting exercise on page 224 of the West textbook "Introduction to Graph Theory". 6.1.15. Construct a 3-regular planar graph of diameter 3 with 12 vertices. (Comment: T. ...
166 views

### When can $L$ sets of the form $\{a,b,a+b\}$ partition $\{1,2,\dots, 3L\}$?

Now also posted to MathOverflow. Consider a set of the form $\{a,b,a+b\}$ where $a$ and $b$ are positive integers with $b > a$. I will refer to such a set as a triplet. Consider now the problem of ...
117 views

### Time complexity analysis of Kruskal's Algorithm

Hello I have a doubt about the time complexity of Kruskal's Algorithm. Symbols: $E \implies$ Total number of edges in the graph $V \implies$ Total number of vertices in the graph $O \implies$ Big $O$ ...
31 views

### How to prove: An extreme point of a face of a convex set $K \subseteq \mathbb{R}^n$ is also an extreme point of $K$ [closed]

How do I prove that An extreme point of a face of a convex set $K \subseteq \mathbb{R}^n$ is also an extreme point of $K$
75 views

### given a binary point, design a quadratic which is minimized at that point!

Given a binary vector $x$, I need to efficiently construct a matrix $A$ such that $x$ is a global minimizer of $z^TAz$ over binary $z$'s. I need the diagonal elements to be positive.
8 views

### Discrete Fast Radon Transform Transpose for Optimization Algorithm

The radon transform of an image $f(x,y)$ can be written as: \begin{equation} p(\alpha,s)=\int_{-\infty}^{\infty}f(x(z),y(z))dz \\ = \int_{-\infty}^{\infty}f(z\sin\alpha+s\cos \alpha , -z\cos \alpha + ...
39 views

### Optimizing a packing of $n$ cliques into $K_n$

In a now-deleted question (previously here), user Lục Trường Phát posted what I thought was an interesting problem from a math competition at their school. To be clear, I don't know anything about ...
24 views

### A Friendly Students Puzzle: Covering $K_{n^2}$ with King's Graphs

The following Question was posed here several years ago: There are 25 students in a class who sit in five rows of five. Each week they sit in a different order. After a number of weeks every student ...
1 vote
109 views

### minimizing a quadratic function with binary decision variables

Suppose that I have a simple quadratic function $f=x^TAx$ and the decision variable $x$ is binary, consider $$\min_x \ f(x) \quad s.t. \quad x \ \text{is binary}.$$ Under what conditions on $A$, a ...
13 views

### Optimal Mass Distribution Minimizing Average 2-Wasserstein Distance to a Set of Mass Distributions

Given a fixed set of $n$ points in 2D (Earth Movers distance Prpblem), $P = \{p_1, p_2, ..., p_n\}$, I am trying to find the mass distribution $\bar{M}$ that minimizes the average 2-Wasserstein ...
567 views

### Maximise $\left( \sum_{i=1}^{n} p_i \cdot i \right) - \left( \max_{j=1}^{n} p_j \cdot j \right)$ with $p$ permutation of size $n$

I'm trying to maximise the following value: $\left( \sum_{i=1}^{n} p_i \cdot i \right) - \left( \max_{j=1}^{n} p_j \cdot j \right)$ where $p$ is an array consisting of $n$ distinct integers from $1$ ...
50 views

### Is this discrete optimization problem NP-complete?

Consider a finite set $A \subseteq \mathbb{N} \times \mathbb{N} \times \mathbb{R}$. Minimize $$\sum_n \left( \max_{(n',i,a) \in A, n=n'} (a + x_i) + \max_{(n',i,a) \in A, n=n'} (-a - x_i) \right)$$ ...
28 views

223 views

### Static Vs. Dynamic Optimization?

I am beginner to optimization and my question is fundamental. We all know that Static optimization means the design variables/objective function does not vary with respect to time. Dynamic ...