Questions tagged [optimization]
Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.
1,873 questions
0
votes
1
answer
44
views
Best strategy with limited ability of memoization
Background
The algorithm to calculate the n-th Fibonacci number using recursion is as follows:
...
4
votes
1
answer
103
views
How to find all maximal rectangles contained in a rectilinear shape on a discrete grid
I would like to find all the maximal rectangles contained in a rectilinear shape on a discrete grid. That is, every rectangle such that, if it were to grow by one cell in any direction, it would no ...
- 41
1
vote
0
answers
64
views
Find a minimal binary tree that satisfies lowest common ancestor constraints
I want to find if there's a fast algorithm for the following:
Given a set of lowest common ancestor constraints, find the smallest (fewest number of nodes) strict binary tree that satisfies all of ...
0
votes
1
answer
87
views
Best mutations for Simulated Annealing on real graph
Here’s what I’m working on: I want to build routes that maximize my custom metrics. I don’t want to share the exact details of these metrics, but for every candidate route I calculate N metrics and I’...
- 1
1
vote
0
answers
32
views
Graph labeling through optimization of a quadratic form
Given a simple unlabeled graph $G = (V,E)$ with vertices $V=\{1,\ldots,n\}$, let $L(G)$ a labeled graph obtained by labeling (with distinct labels) the vertices of $G$ through any $l: V \rightarrow V$ ...
- 155
0
votes
0
answers
38
views
Is my implementation of the Richard Korf's bidirectional iterative-deepening depth-first-search (BIDDFS) correct?
This post is about correctness of the BIDDFS (bidirectional iterative-deepening depth-first search).
I got this idea from a Richard Korf's paper. Before answering, I suggest you first read this.
My ...
- 60
4
votes
0
answers
75
views
Remove contiguous 5th powers (5-fold repetitions) from list of 'a's and 'b's?
Given a list of characters in $\{a,b\}$, for example $abababababa$, what is the most efficient way to remove all 5th powers in a way that makes the string as short as possible?
(This example would ...
- 141
2
votes
0
answers
57
views
Testing hidden connectivity of vertex pairs in graph
I have a problem from graph theory for which I could need some theoretical background and,
if possible, ideas for an algorithm.
Suppose we have a "usual" graph $G =(V,E)$ with finitely many ...
- 181
4
votes
1
answer
215
views
Algorithm to maximize sum of absolute dot products over the unit sphere
Given vectors $x_1, \dots, x_n \in \mathbb{R}^d$, I am seeking a solution to the following optimization problem:
$$ \underset{v \in \mathbb{R}^d}{\arg\max} \sum_{i=1}^n \left| \langle v, x_i \rangle \...
- 43
0
votes
1
answer
82
views
Variation of Knapsack problem that finds minimum value instead
Imagine this variation of the knapsack problem:
Given a set of n items and a container that requires a minimum weight of W, where each item has a weight w and value v, find a set of s items with a ...
1
vote
0
answers
45
views
More Precise Interval Analysis
I am building an inference engine that uses interval analysis to compute variable bounds. Efficiency is very important in my case:
I cannot use SMT solvers
I cannot afford full enumeration, since ...
- 11
2
votes
2
answers
126
views
Binary jumping line function intersection minimum search
Algorithm description: Start with a random point of a function and find horizontal line that passes through it. Jump large amount down (or multiple times (and increasing) if needed) until we are under ...
5
votes
3
answers
2k
views
Avoid brute forcing all combinations for this optimisation problem
I have a real life problem where I need to join two data sets such that the absolute difference between keys is minimal.
Technically: we have DS1 and ...
- 173
0
votes
0
answers
28
views
Is direct fatoradics to find the nth lexicographic permutation possible?
I have been using an algorithm from here to find the nth lexicographic permutation of a set.
One part of the algorithm that I have been wondering about is the part where elements are pushed to a new ...
- 111
1
vote
0
answers
44
views
Upper bound on a tree containing sum nodes and choice nodes, requiring consistent choices across subtrees [closed]
I have a tree containing sum nodes, choice nodes and point nodes. I'd like to maximize the number of points at the root of the tree.
The value you get for a point node is the number of points on that ...
- 111
0
votes
1
answer
87
views
solution to a variant of jump game
I have a question,there are 2 arrays a and b of the same size n.a[i] is positive and b[i] represents the maximum length of jump allowed from index i.you start at index 0 on the array a.if you land on ...
- 3
0
votes
0
answers
50
views
Recurrence arising from Acceleration
In the original proof for acceleration (using plane-search), the following step (from (2.6) to (2.7)) starts with
$$
\sum_{I=1}^N \frac{v_i}{\sqrt{v_i - v_{i+1}}} \leq C(N)
$$
and concludes that $v_{N+...
- 46
0
votes
0
answers
44
views
Is my calculation of the number of functions for 𝐹 ( 𝐴 𝐵 𝐶 , 𝑟 , 𝑘 ) and 𝐺 ( 𝐴 𝐵 𝐶 , 𝑟 , 𝑘 ) correct?
I’m working on a problem involving dynamic programming in graphs. The sub-path (ABC) has vertex weights and edge lengths, and we are tasked with calculating the optimal cost of a (k)-center.
Given (k =...
1
vote
0
answers
53
views
Optimal cycle for minimizing distance between vectors
I faced this problem recently, and am looking for an efficient solution.
We are given $X = (x_1,...,x_n)$ and $Y = (y_1,...,y_n)$ two vectors with ascending coordinates.
Considering a cycle $\sigma = (...
- 11
1
vote
1
answer
139
views
Algorithm for The Ticket to Ride Problem
The Problem
Given a connected graph $G=(V,E)$, edge weights $w:E\rightarrow\mathbb{N}$, and a set of vertex pairs $T=\{\{t_{1a},t_{1b}\},\{t_{2a},t_{2b}\},...,\{t_{ka},t_{kb}\}\}|t_{ij}\in V$, find a ...
- 123
1
vote
0
answers
33
views
Conditions on LR in Gradient Descent
In Introductory Lectures in Convex Optimization by Yurii Nesterov, Section 1.2.3 shows that gradient descent is guaranteed to converge if the step size is chosen either with a fixed step size or ...
- 11
0
votes
1
answer
56
views
Finding inputs for equal outputs in monotonically decreasing functions
I have $n$ functions, $f_1,\dots,f_n$. Across these, I want to allocate a known amount $I$ so that $i_1 + i_2 + \dots + i_n = I$ and $f_1(i_1) ≈ f_2(i_2) ≈ \dots ≈ f_n(i_n)$ (equal up to a certain ...
- 333
1
vote
0
answers
86
views
Data structure for tracking boolean clauses size
Given an unordered sequence of n boolean conjonction clauses which may contain duplicates, I am looking for a data structure that would track the number of clauses grouped by the number of variables ...
- 11
0
votes
1
answer
51
views
Smart Boot: a kernel function to SAVE / LOAD ALL the needed working RAM from the disk
Boot process is wonderful, but quite tedious to wait the kernel reload every needed objects on the RAM again.
One day, I was wondering if it was possible the kernel to "take a snapshot" of ...
- 101
0
votes
1
answer
106
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