Questions tagged [optimization]
Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.
1,838
questions
1
vote
0
answers
10
views
Constrained optimization with batches/chunks?
Suppose I have $n$-dimensional real vectors $\mathbf u$, $\mathbf v$, $\mathbf w$, with $\mathbf v>0$. I'd like to maximize the following function $f$:
$$
f(\mathbf x)=\sum_{i}(u_ix_i-v_ix_i^2)\...
- 11
0
votes
0
answers
43
views
How to optimize this sorting algorithm?
I try to sort elements in a specific way which is basically inherently recursively defined. That is to say which element $x_n$ from the input array assumes index $i(n)$ in the output array is a ...
0
votes
1
answer
38
views
Do computers have an optimal circuit for 64bit addition?
Addition is implemented in computers using a circuit of logic gates.
Do we know what is the lowest depth circuit possible for 64bits?
And is it used in practice?
- 1
0
votes
0
answers
15
views
Best algorithm for sportstrainer-software
What is the best algorithm for my case?
I have one tennis-trainer, which has same weekly timeslots available for his students. His timeslots are x hour a day. Say mo-fr 6-9 PM saturday and sunday 10 ...
1
vote
1
answer
25
views
In reinforcement learning, does policy affect the maximization of the value?
Though the reward was assigned by the environment, the once the policy $\pi$ was fixed, the probability of the action on the states $\pi(a|s)$ could be assigned.
However, this meant given different ...
0
votes
0
answers
10
views
Why does it satisfy the definition of a subgradient vector in a flow network problem
Hello everyone, I need to clarify some doubts. I was reading the article 'Subgradient Optimization Methods in Integer Programming with an Application to a Radiation Therapy Problem.' This is my first ...
- 1
1
vote
0
answers
21
views
Find a basis of a vector space minimizing the numbers of nonzero coordinates for a bunch of vectors
I've got a (to be a bit specific) 84-dimensional rational vector space, and as many as 1197 vectors in it. In the basis of the space that I've got, numbers of nonzero coordinates for these vectors ...
- 111
1
vote
0
answers
15
views
Is it possible to start a Dijkstra search from a source node s, bounded at r, with a non-empty distance map and priority queue?
TL:DR: I want to know whether correctness is affected if I start Dijkstra with a distances map that already contains shortest paths shorter than $r$ and a priority queue initialised with those ...
- 11
0
votes
0
answers
18
views
Optimization with a minimal, unreliable dataset
I'm attempting to make an optimization algorithm for machine alignment that uses piezoelectric motors to work. Essentially, I gather the net movement of my motors on two axes and the resulting ...
1
vote
1
answer
31
views
Extract dominant value per column with single value per row in a matrix
Given a matrix $A \in \mathbb{R}_{+}^{n \times m}$ where $m \geq n$.
I want to convert it into a form where there is a single $1$ per row yet no more than a single $1$ per column.
The logic is convert ...
- 13
0
votes
1
answer
29
views
Fit data to a lookup table
I have been looking for methods to fit 1-D data to a lookup table. In other words, there's no known function that is used as a model.
For example in the plots below, the measured data (blue) is fit to ...
- 1
1
vote
1
answer
52
views
Is this graph grouping problem $\mathsf{NP}$-hard?
Let's introduce the notion of layer: given a simple graph $G$ a layer is a subgraph of $G$ satisfying the following property:
If any pair of vertices is connected with an edge, these two vertices ...
- 1,966
2
votes
1
answer
88
views
Minimum Cell Changes to Ensure Unique Numbers in Each Row and Column of an $ n \times n $ Table
We have an $ n \times n $ table, and in each cell of the table, there is a number from $1$ to $ 2n $. We want to change the numbers in some of the cells and replace them with other numbers from $1$ to ...
- 157
0
votes
1
answer
51
views
How do computer scientists finds a minimum of a tuple?
In multiobjective optimization, what does it mean to minimize a function of the form $F(a)=(O_1,-O_2,...,O_n)$? I mean, in mathematics, we can order every set by Zorn's lemma but I think we need some ...
- 11
2
votes
3
answers
76
views
How do computer scientists find a minimum of a tuple?
In multiobjective optimization, what does it mean to minimize a function of the form $F(a)=(O_1,-O_2,...,O_n)$? I mean, in mathematics, we can order every set by Zorn's lemma but I think we need some ...
guest
0
votes
1
answer
25
views
Is the time complexity of greedy set cover polynomial or pseudopolynomial?
I have been studying the set cover problem for sometimes and see that its greedy algorithm has a big O complexity of $O(M^2N)$ from this post. However, it seems too good to be true since this is an NP-...
0
votes
1
answer
19
views
Matrix optimization to minimize pruing satifying column constraints
Suppose we are given a matrix $A = [a_{i,j}]_{n\times m}$, where all entries are non-negative. In this matrix, we are allowed to exchange two elements, $a_{i,j}$ and $a_{i,j'}$, sitting in the same $i$...
- 1,934
5
votes
0
answers
109
views
Minimum cost path connecting exactly K vertices
I came across a situation in real life that maps to this optimization problem:
Given a fully connected, undirected, weighted graph with $N \ge K$ vertices, find the simple path connecting exactly $K$ ...
- 51
5
votes
2
answers
1k
views
Global optimization of state assignments in a directed graph with a tree-based distance cost
I am exploring a general optimization framework to solve problems characterized by the following structure. Any literature references, search terms, or algorithmic strategies would be greatly ...
- 151
0
votes
0
answers
23
views
Time complexity of optimal index
Consider a data structure that stores a set of $n$ objects, where each object is a map of arbitrary key-value pair.
The data structure maintains a reverse lookup table, where for each key-value pair, ...
- 133
2
votes
1
answer
57
views
Minimize cost for list of words given a list of letters
What is a general algorithm to reorder a list of letters such that it minimizes the cost for a fixed list of words?
Algorithm input
To be optimized
a list of unique letters: ...
- 141
3
votes
1
answer
207
views
How to find a binary vector with minimized distance with a vector set?
Given a set of vectors $S = \{v_1, v_n, ..., v_n\}$, $v_i \in \mathbb{R}^m $. Now I want to find a binary vector $ t \in \{0, 1\}^m $ to minimize $ \sum_{i=1}^n \text {distance} (t, v_i)$.
...
- 33
3
votes
2
answers
68
views
Generating all unique permutation cycle types and their weights
Consider the set $1, 2, \dots, N$, where $N>1$ is a natural number. In general, there are $N!$ permutations of this list. Let $\sigma$ be one such permutation. We define the tuple $\varphi(\sigma) =...
- 33
2
votes
1
answer
75
views
Conditional Maximization of a Binary Matrix
Given an $L \times N$ matrix $A$ with only binary values, $A_{ij} \in \{0, 1\}$, and a vector $b$ with $b_j = 2^{j-1}$, I want to find a matrix $\tilde{A}$ that maximizes $\tilde{c}=\tilde{A}b$, ...
- 61
0
votes
1
answer
20
views
Assigning classes to nodes in a graph to minimise intra-class distance
I have an complete undirected graph with n vertices, and the edge $(u,v)$ has weight $d(u,v)$ for some distance function.
I also have $m<n$ elements, each of which belongs to a category $\{1...i\}...
- 1
1
vote
1
answer
113
views
Prove that Gaussian elimination solves maximum XOR subset problem?
Given an array of positive integers. Find the subset that maximizes the XOR of all of its elements? This can be solved by "Gaussian elimination" in the following manner:
Pick the largest ...
-3
votes
1
answer
193
views
Can every greedy problem be solved using dynamic programming?
Can every problem with a greedy solution be solved using dynamic programming? Why or why not?
I'm not completely sure how to formally reason about this, my understanding about the structure of ...
0
votes
1
answer
44
views
Regular branch and bound vs integer programming branch and bound
In the context of linear integer programming, we have a branch and bound algorithm described here. This involves solving the non-integer constrained linear program and successively introducing ...
- 377
2
votes
2
answers
108
views
No Neighbor Vertex Cover
Let $G=(V,E)$ be an undirected connected graph with a set of vertices $|V|$ and a set of edges $|E|$. A set cover $D$ satisfies $D \subseteq V$ and $uv \in E \implies u \in D \lor v \in D$. A variant ...
0
votes
1
answer
44
views
How can I reduce the complexity of an inverse DFT where I have a uniform frequency series being evaluated at non-uniform target points?
I have implemented an N-dimensional Non-Uniform Discrete Fourier Transform (in this case it's specifically an inverse NUDFT) using PyTorch. My goal with this implementation is to have a function which ...
- 101
1
vote
1
answer
23
views
Best internal representation of a random variable to enable iterative sampling and interpolation/regression
Let $[0,100]$ denote the interval of real numbers between $0$ and $100$. Given a function $f:[0,100]^n \rightarrow \mathbb{R}^+$, I want to implement the following simple algorithm to search for the ...
- 113
2
votes
2
answers
124
views
Prove that balanced binary search tree has lowest expected cost
Take numbers from 1 to 100. Put all of them in a binary search tree. Now, one of those 100 numbers is picked uniformly at random and given to us. We'd like to find it in the binary search tree. The ...
- 377
4
votes
2
answers
132
views
Finding optimal sequence of attacks to minimize number of soldiers needed
The problem
Trying to improve my algorithms I bumped into a problem by Pedro Pablo Gómez Martín and Marco Antonio Gómez Martín, which I can summarise like this:
You are given a list of enemy bases ...
- 263
2
votes
1
answer
361
views
Potential of Artificial Intelligence to improve algorithm for PI
Recently AI (alphazero) was used to improve practical matrix multiplications by around 10 to 20 percent. Alphageometry and ramanujan machines all came into existence in the recent years as well. Seems ...
- 121
0
votes
0
answers
26
views
Given two paths, how can I merge them in a Divide-and-Conquer algorithm to find the optimum earning route given a set of points with rewards?
The problem statement is the following: given a non-empty set P of (x, y) points with an associated reward, find the path through P that gives the maximum earning. The earning of a path is the sum of ...
0
votes
2
answers
68
views
Iterative minimization algorithm to find a target among a set of points
I would like to find a target point in a 3-dimensional space. I do not know the exact location of the target, but I can measure to it from some of the points in the space with a metric that roughly ...
- 117
2
votes
1
answer
69
views
Covering a graph with M cliques maximizing total edges weight
I am working on a problem that involves distributing a set of N supplements across a predefined number of meals (M) in a way that maximizes the total number of positive interactions and minimizes ...
- 23
0
votes
2
answers
312
views
Find minimum of a function only knowing the ordering of a set of input points
Suppose I have a function $f: \mathbb{R}^n\rightarrow\mathbb{R}$. All I know about the function is, I have a set of pairs of vectors ($\vec{v}_a$, $\vec{v}_b$) for which I know which one is greater (i....
- 9
1
vote
0
answers
29
views
The problem of finding a local minimum of a function
I wrote code for the Regular Simplex (RSM) and the Irregular Simplex (Nelder-Mead Method (N-MM)) in Visual Studio in C++. For given functions (quadratic (QF), Rosenbrock with alpha = 1 (RF1), ...
- 11
3
votes
1
answer
235
views
How to optimize algorithm to solve the following time series problem?
I am working on a project and came across the following problem I have to solve.
Imagine we have a time series data Ts which is an array of pair, say each element ...
0
votes
0
answers
121
views
Algorithm for "Clustering" a directed graph
I have a directed graph with unweighted edges between the vertices, and possible cycles.
I want an algorithm that I can pass in the graph and a number N, and have it spit out a set of N clusters each ...
- 85
1
vote
0
answers
73
views
Optimization of value over network flow from start to end node with constant function multiplier edges tractability
Our problem is similar to this, but it details various approaches we can make.
The problem also was formulated operation research, but got hit with numeric limitations.
...
- 111
-3
votes
1
answer
118
views
The cost of an algorithm
Please tell me what is the correct formula for calculating the cost of an algorithm? I used this: number of calculated functions + 4 * number of calculated function gradients + 8 * number of ...
- 11
2
votes
0
answers
85
views
Monotone boolean satisfiability problem : finding minimal solutions
I am very interested in the following questions, which sprang out from the topological study of loops in surfaces and their intersection numbers.
Consider, over a finite set of boolean variables $X$, ...
2
votes
1
answer
62
views
"Consecutive statements" in Static control Part(SCoP)
Context:
I was reading a research paper related to polyhedral representation(citation given in last). Got confused while trying to understand the notation by implementing them with example code.
Paper ...
- 123
2
votes
0
answers
49
views
Max min diversity on points taken from line segments in the plane
If I start with $n$ different points $P_1,\ldots,P_n \in \mathbb{R}^2$ and want to select a set $X$ of cardinality $m \leqslant n$ from them subject to the condition that the value
$$d_\text{min}(X) = ...
- 161
1
vote
1
answer
48
views
Can PTAS be used to optimally solve Knapsack?
Suppose you have a Knapsack (optimisation) problem with integer values and weights, and you know the optimal value $OPT$. Can you compute an optimal solution in polynomial time by using a PTAS or ...
- 807
1
vote
0
answers
74
views
Optimal Data structure for queries involved rectangles and cartesian coordinates
What data structure would be optimal in terms of time and space for the following usecase:
Given information about rectangles in the form of- {rectangle_id,left_bottom_corner_x, ...
- 11
0
votes
3
answers
64
views
Is there an algorithm to implement N-input-gates using smaller gates?
To borrow part of a description from a similar but distinct question: there exist 2^(2^N) different functions which accept N binary inputs and return a 1 bit output. For the purposes of my question I ...
2
votes
0
answers
118
views
SCoP, Iteration Domain in Polyhedral Optimization and use of Presburger arithmetic
Context:
While exploring the fundamentals of polyhedral optimization and attempting to explore a connection from the input Static Control Part (SCoP) to the iteration domain from birds eye view, I am ...
- 123