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

932 questions
Filter by
Sorted by
Tagged with
1 vote
19 views

### Can this problem adjust to a Bin Packing problem?

hope you are doing fine. I am facing some mathematical problem which I am not certain of which type is it, nor how to approach its solution. Here is a picture with a representation (simplify) of the ...
• 111
19 views

### Find the closest stack total weight where number of n values should be the same in all stack

Lets say I have potatoes with weight 7,5,4,8,12,10,4,8,12,12,13,12 I want to stack them in the way that all the stacks weight should be closest possible condition each stack should have equal amount ...
1 vote
56 views

### Find the cheapest arrangement of non-overlapping colored rectangles necessary to achieve a sequence of colors behind holes

Input Let the input be a sequence of colors with any length at least 1. For example, (red, blue, red, green, blue). Each color is represented in the input as a string, not as any abstract notion of a ...
1 vote
50 views

### To find the maximum possible value of their greatest common divisor $\gcd (a_1,a_2,\cdots, a_7)$.

The sum of seven distinct positive integers $a_1,a_2,\cdots, a_7$ is $315$. To find the maximum possible value of their greatest common divisor $\gcd (a_1,a_2,\cdots, a_7)$. If they were all equal ...
• 11.9k
1 vote
32 views

### Which $n^2$ points of a finite grid minimize average $L^1$ distance to a uniformly drawn point?

This is a correctly tagged repost of my question I asked yesterday. I came across the following problem: Given a finite grid in $\mathbb{N}^2$ (or equivalently $\mathbb{Z}^2$) consisting of $a$ rows ...
• 459
119 views

### No Dijkstra and no BFS? What else is there?

So, this is the scenario I have a graph with 7 points (say A to G) all interconnected (full mesh), and I want the best path to traverse all points starting from A and ending on G, but there are a ...
1 vote
15 views

### Why is the size of a minimum vertex cover always greater than or equal to a maximal matching?

The topic I am dealing with right now is a 2-approximation algorithm for the minimum vertex cover. The proof seems fairly simple but I don't understand one assumption that is made. It is the ...
• 319
18 views

### Is there a formula for the number of "faces"/boundaries of an hypercube defined by a multidimensional grid?

Consider a D dimensional grid, $X = X_{1} \times X_{2} \times ... \times X_{D}$. Denote the size of $X_{j}$ with $| X_{j} |$. What is the formula for the number of "faces"/boundaries of ...
1 vote
24 views

### Multi-objective optimization by using the optimal values of individual function

We want to minimize the following function: \begin{align} &\min_{x_1,y_1,x_2,y_2} \underbrace{\frac{x_1^2+y_1^2+x_2^2+y_2^2}{(x_1y_2-x_2y_1)^2}}_{f}+(\alpha-1)\underbrace{\frac{(x_1+\beta y_1)^...
• 13
1 vote
36 views

### How do you represent the number of iterations in the formulation of an optimization problem?

Let's say I want to minimize some function for f(x), with respect to x, in the minimum number of iterations. How would I represent the number of iterations in the formulation of this optimization ...
• 133
155 views

### An efficient algorithm to generate a set of tuples satisfying a given upper bound for a distance between two arbitrary elements

Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates)....
26 views

### Christofides Algorithm for the TSP: A "polynomial time approximation algorithm"?

I'm currently studying the travelling salesman problem and Christofides algorithm. I think I understand that TSP is an NP-hard problem, and so the complexity of calculating a solution grows ...
• 187
31 views

### Assignment Problem: Roles and Candidates with Salary Budget

The problem: A company has $n$ roles to be filled. There are $m$ candidates. Each candidate $c$ the company hires may fulfill one or more roles. Each assignment of a candidate $c$ to a role $r$ ...
• 497
45 views

### Discrete Optimization Problem: What is the optimal course schedule?

Linda Johansen, an incoming first-year MBA student, would like to determine her course schedule for her first two semesters of business school. Linda has created a list of twenty potential courses ...
38 views

### How to sort into X bins Y times with minimum overlap?

Let's say I'm hosting a series of dinner parties for a total of $N$ guests. Each night, there are $X$ tables, and we are meeting for a total of $Y$ nights. I want to preassign the guests to tables ...
• 3,908
23 views

### Need help in using optimization theory to solve variables

$$\lvert H(f)\rvert=K\lvert\frac{1}{t_1^4}e^{-j2\pi ft_1}+\frac{1}{t_2^4}e^{-j2\pi ft_2}+\frac{1}{t_3^4}e^{-j2\pi ft_3}\rvert (1)$$ where K is constant,$|.|$means amplitude.I have the image of the ...
26 views

### Looking for resources on Dynamic Generalized Assignment problem

I'm trying to find previous research on the dynamized version of the Generalized Assignment Problem. That is, how to efficiently maintain an optimal solution in the case where existing workers can be ...
28 views

### Maximum flow with minimal number of vertices used

In many of the research problems I encountered recently, the following version of the minimum cost maximum flow problem came up. We are given a directed graph $D$, a source vertex $s$ and a terminal ...
• 43
26 views

• 213
62 views

### Finding Minimum Spanning Tree in O(n+m) time

I am now learning about MST and algorithms for finding it, like Prim's, Kruskal's and etc. However, what if we have a connected, undirected simple graph and all edges have a weight, BUT the possible ...
• 21
1 vote
52 views

### Beatrix's board and holes

This is the last question from UKMT's JMC 2016: Beatrix places dominoes on a 5 × 5 board, either horizontally or vertically, so that each domino covers two small squares. She stops when she cannot ...
• 5,041
27 views

### Route Planning algortihms and optimization

Not sure if this is the right place to ask, but I have the following math-related problem. We need to schedule deliveries, about 20 per week. We have varying van availability, one with a capacity of 3 ...
85 views

### Prepare all dishes with the least different ingredients - what is this problem called?

I am trying to find the best way to solve the following problem: A cook has to prepare $n$ dishes, and for each dish he has $k$ different recipes. Each recipe is a non-empty subset of the set $I$ of ...
• 23