Questions tagged [optimization]
Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.
1,712
questions
1
vote
1
answer
29
views
Placing K gas stations among n cities to minimize distance
There are $n$ cities on a highway with coordinates $x_1$
, . . . , $x_n$ and we aim to build $K < n$ gas stations
to cover these cities. Each gas station has to be built in one of the cities, and ...
0
votes
0
answers
40
views
Budgeted min cost max flow in bipartite where the flows must also be a matching set
I'm trying to find a problem description that is roughly akin to a budgeted min-cost max-weight bipartite matching where the capacities are greater than 1. Imagine a max-flow problem on a graph that ...
1
vote
1
answer
21
views
Writing an Algorithm to Represent a Bit Matrix in Minimal Operations?
I am trying to come up with an algorithm to find the minimal representation of the transformation from a zero matrix to a target matrix.
Specifically, I have an empty matrix and can perform operations ...
- 11
2
votes
1
answer
30
views
Finding the smallest subset s.t. all elements satisfy condition, using as few tests as possible
I'm having a hard time describing this problem without an example, so let's go with this: Say you have a program that is made up of many files. There are some files you could delete, and, while it ...
- 21
0
votes
0
answers
19
views
How to optimize an approximated matrix multiplication?
Suppose the objective I try to maximize is
$$\max_{X} \|(I - \alpha X)^{-1}XA\|_F$$
where $X$ is the matrix needs to be pinned down, $\alpha$ is a scalar, and $\|\cdot\|_F$ is the Frobenius norm. Note ...
1
vote
1
answer
49
views
Given required total area and capacity, choose an amount for each of three given modules
Suppose you have three modules $m_1,m_2$ and $m_3$, each with a capacity of $c_i$ and area $a_i$. You are also given $A$ and $C$. How can you find some of the solutions to choose an amount of each ...
- 11
0
votes
1
answer
26
views
find maximum in arbitrary expression tree
Originally posted on SO.
I have a very simple language that gets compiled to an Expression tree, and then evaluated. Users can define mathematical operations, use variables and control flow. Moreover, ...
- 101
0
votes
0
answers
30
views
Translating math notation from paper into something more accessible to a layman
I have been struggling trying to understand this differential geometry paper:
https://cseweb.ucsd.edu/~alchern/projects/MinimalCurrent/MinimalCurrent.pdf
I would like to ask for someone with more ...
- 143
1
vote
1
answer
51
views
How to schedule ELO-based, fair games with n players and dynamic teams?
The setting is the following: There are n players that want to compete in a specific game over the course of an event. A game is played between 2 teams of 2 players each (so a 2v2). Each player as a ...
- 13
2
votes
1
answer
93
views
Dynamic programming: optimal order to answer questions to score the maximum expected marks
You have $n$ questions in an exam. Question $i$ is answered correctly with probability $p_i > 0$. If question $i$ is answered correctly, you get $R_i$ marks. You can choose to answer
the questions ...
- 23
0
votes
1
answer
31
views
Is there an optimisation algorithm that does not require a good initial solution?
I was reading this question on CS stack exchange called How important is initial state for local search optimisation?
I would like to extend it with the following example:
I have been reading about ...
- 3
2
votes
0
answers
42
views
Designing Shortest Route
Suppose we have a metric space $(X,d)$ and we call $r$ to be a root vertex and then there are $n$ clients(i.e. $n$ vertices/nodes) who need packages delivered to them from $r$. The $i$th client ...
- 43
0
votes
0
answers
16
views
Linear Optimization With Two Variables, given starting Values
Let's suppose we are given the following inequalities:
3x + 7y <= 71
4x + 9y <= 21
...
and so on, in the above format. The coefficients and the value ...
2
votes
0
answers
55
views
Permuting matrix entries to lower rank
Suppose I have a rank-$k$ matrix $A \in \mathbf{R}^{m \times n}$. Now suppose this matrix has its elements shuffled by an adversary to maximize the rank. Is there a way to reverse this permutation and ...
- 43
1
vote
1
answer
39
views
Minimize bottleneck in flow network
Let $G=(V,E)$ be a flow network with two vertices $s,t$ also each edge has its capacity equal to $\infty$. Our goal is to transfer a flow of size $C$ from $s$ to $t$ so that minimize an edge that has ...
- 1,556
1
vote
0
answers
23
views
Suggestion for tools/libraries for multi-output boolean circuit minimization?
I am interested in the following problem
Input: A boolean function F with n boolean inputs and m boolean outputs.
Output: A circuit C implementing F such that C has as few gates as possible.
The ...
0
votes
1
answer
36
views
Compute the maximum length of an increasing digital subsequence given an array of digits
Consider the following exercise from chapter Dynamic Programming in the book Algorithms by Jeff Erickson.
Let $D[1 .. n]$ be an array of digits, each an integer between $0$ and $9$. A digital ...
- 1,556
0
votes
0
answers
9
views
fault-tolerant K-median problem on an undirected graph
We know that the K-median problem is proved to be NP-Hard. In fault-tolerant K-median problem on an undirected graph $G=(V, E)$:
We are given a set of facilities $F\subseteq V$ and a set of demands (...
- 1
1
vote
1
answer
138
views
Finding Optimal Configuration of Formula without trying every Permutation
I have a math problem I need to solve so I can complete an optimisation in a computer program. My initial approach was just to brute force all the possible permutations but it got out of hand quite ...
- 129
1
vote
1
answer
69
views
Ordered open-end knapsack problem optimised for minimum weight range
Given a fixed number of infinite-capacity containers and a list of items of varying weights, how can I best place the items into the containers preserving their original order in a way that minimises ...
- 113
1
vote
1
answer
63
views
Algorithm for a modified worker-task assignment problem with groups of tasks and substitutability between tasks within groups
I'm looking for an algorithm to solve a modified version of the assignment problem. It differs from the standard assignment problem in that the modified version has groups of tasks instead of just ...
- 13
1
vote
1
answer
51
views
What data structure/s can I use for fastest lookup of a permutation between two arrays of pairs (preserving order)?
I'm trying to figure out a more efficient solution to the following problem.
Dataset: A set of arrays of key-value pairs (K, V). The arrays have varying lengths, ...
- 111
0
votes
0
answers
77
views
Traveling salesman problem with dynamic edge costs
General description
I have an optimization problem in which I need to schedule events and each of the events needs to be scheduled exactly once. The "cost" of scheduling one event depends on ...
- 101
1
vote
1
answer
55
views
A kind of generalised assignment problem where we minimise error relative to a goal "weight"/"value" - how to solve it?
I apologize if I did not use the terminology entirely correctly in the title. This problem seems to me quite similar to an assignment problem and likely something that occurs in real life in business.
...
- 11
1
vote
0
answers
21
views
tight lower bounds of parallel machine scheduling with gang scheduling constraint
I am interested in tight bounds for the Parallel Machine scheduling problem with a gang scheduling constraint.
In the notation of Graham, Lawler, Lenstra and Rinnooy Kan, this might be called $Pm|\rm{...
- 17.5k
1
vote
1
answer
36
views
Minimal Number of Transactions to Settle Outstanding Poker Game
There are several players at the end of the poker night with wins and losses, with zero sum. What is the optimal solution to settle the balance that minimize the total number of transactions (eg. if ...
- 143
0
votes
0
answers
24
views
Distribution of items in ordered list with respect to constraints
I have a very specific problem and Im desparate for help, I've been working part time on it for almost a year without almost any success, I'll do my best to describe it as thorough as I can
Our input ...
1
vote
0
answers
23
views
Creating an Influence Map within a bounded Space
I am not sure if this is a math question or a computer science question, so please direct me to a better suited community if needed.
Given a bounded space G,and a set of points P, I want to create two ...
- 11
1
vote
1
answer
34
views
Boolean Integer Linear Optimization/Programming
Trying to solve an ILP optimization problem with a number of potential boolean variables and then express constraints on these variables based on those boolean results.
Let's say I am doing 5 coin ...
- 11
0
votes
1
answer
26
views
Finding the best algorithm for nearest neighbor search in a 2D plane with moving points
I am looking for an efficient way to perform nearest neighbor searches within a specified radius in a two-dimensional plane. According to Wikipedia, space-partitioning data structures, such as :
k-d ...
- 219
1
vote
2
answers
26
views
Optimize Multiple Agents Completing Multiple Tasks in Parallel
I have an optimization problem and I am wondering if there is a better way to solve it than using a naïve brute force method. I have a number of tasks T that must be completed, and a number of agents ...
1
vote
1
answer
64
views
Two statements about optimal binary search trees
This is a paragraph from the book CLRS:
What we need is known as an optimal binary search tree. Formally, we are
given a sequence $K = (k_1, k_2, ..., k_n)$ of $n$ distinct keys in sorted order (so ...
- 411
1
vote
0
answers
37
views
Find the smallest Valeriepieris circle
The Valeriepieris Circle is a circle within which it is supposed that the majority of the World's population lives. I'm interested in general-case and average-case algorithms for finding such a circle....
- 133
2
votes
2
answers
116
views
Why isn't there a computational "Carpenter's Algorithm" for Planar Convex Hull?
Planar Convex Hull is a problem where you have $N$ points in a Cartesian plane, and you want to find the smallest convex polygon that encloses the points. QuickHull seems to be the best available ...
- 23
2
votes
1
answer
49
views
Java optimization and minimization
I'm new to optimization and I have a little problem that I want to resolve with my job. Here we go!
I need a certain number of drivers per day and each driver has 2 consecutive days off during the ...
- 23
1
vote
0
answers
57
views
Finding $\text{argmin}_{x\in \Delta_n} ||A x -y||^2$
Let $\Delta_n :=${$x\in \mathbb{R}^n\colon \sum_{i=1}^n x_i = 1$} denote the probability simplex in $\mathbb{R}^n$ and $A^{n \times n}$ be diagonalizable matrix.
I would like to know what is the ...
- 121
1
vote
1
answer
121
views
Sorting a collection of tuples using merge rearrangements
Given a collection of tuples $X=\{(x_1,y_1),\dots,(x_n,y_n)\}$, where elements
$x_i, y_i \in R_{\geq 0}$ are non-negative real values. The collection $X$ is
sorted if $x_i \leq x_{i+1}$ and $y_i \leq ...
- 123
0
votes
0
answers
16
views
Matching to Optimise HOTA
I'm trying to understand HOTA: A Higher Order Metric for Evaluating Multi-Object Tracking and in particular the section "Matching to Optimise HOTA" on page 8.
There is a paragraph that says:
...
- 101
0
votes
1
answer
43
views
Algorithm to distribute group of connected nodes in a graph
Given something similar to this.
Where you have blocks (the squares) and entries (the circles). Each block has a rating (the number inside the blocks) and is connected to other blocks. This topology ...
- 1
1
vote
1
answer
32
views
What is the name of the complexity class for the optimization version of co-NP-complete and coNexpTime-complete problems?
I know that the optimization version of NP-complete problems belong in NPO. What about co-NP-complete problems? Is there a co-NPO class, or is it just NPO?
I've also never seen the name for the ...
- 13
3
votes
1
answer
63
views
Finding a minimal set of package versions in a dependency graph with constraints
Suppose you have a dependency graph of "packages" registered in the ecosystem of a given programming language. We can model each package as a tuple ...
- 133
5
votes
2
answers
612
views
Compute Permutation Number
Given a permutation on the array of integers 1 through n, I want to find the index of the permutation in a list of all possible permutations of those integers, sorted in lexicographic order.
For ...
- 120
2
votes
3
answers
115
views
Algorithm: Optimal selection of subset of nodes in undirected graph to minimize score
Apologies if this question exists somewhere. I'm sure it's been asked, but I don't know how to search for it. This is not a homework question but rather a scientific problem I ran into. If this is a ...
- 123
0
votes
2
answers
98
views
Time complexity of finding the minimum by dynamic programing
How can I calculate the complexity of computing $MD(b)$, where $b=(b_1,b_2,\dots,b_n)$?
$$MD(s) = \max(s)-\min(s) + \min(MD(s\setminus\{\max(s)\}), MD(s\setminus\{\min(s)\}))$$
where $s$ is a finite ...
- 37
0
votes
0
answers
16
views
The maximal choice smallest grammar algorithm. Is this an exact algorithm or an approximation?
When we speak of a variable, sometimes we will mean the string it expands to, and other times, the variable itself. Let $t \leqslant s$ mean substring.
Take the string $s = a^6$. Then its ...
0
votes
0
answers
28
views
An ingenious exact smallest grammar algorithm for strings over a single letter, $s \in \{a\}^*$. First enumerate the start rules up to commutation
Take $s = a^{10}$ for our example string. Compute the set of all potential grammar reducing variable-rules:
$$
A \to aa \\
B \to aaa \\
C \to aaaa \\
D \to aaaaa
$$
There is always exactly $\left\...
-1
votes
1
answer
45
views
how to find the most optimal path for this problem?
There are N islands and there is one pirate. The pirate can start out from any one of the n islands and has the option of either staying on the same island for the next day or moving to a different ...
- 1
1
vote
1
answer
44
views
Possible approaches to the Ship City problem?
About few ago in my freshman year of college I stumbled across an an old blog post on r/programming posing a programming challenge. Here is the short version of it:
Hundreds of ships would like to ...
- 11
2
votes
0
answers
35
views
State of the art implementations of minimum-cost multicommodity flow approximation algorithms
I'm looking for implementations of approximation algorithms (or algorithms that would be meaningful to implement for use in practice) for the minimum-cost multicommodity flow problem as defined in e.g....
- 165
1
vote
0
answers
30
views
How to let the champion sit?
There is a chess tournament planned. It is a single-elimination tournament, and for spectacle purposes, only one match at a time will take place, on a table in the middle of the stage (winners will ...
- 11.8k