Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [optimization]

Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

Filter by
Sorted by
Tagged with
0 votes
0 answers
21 views

Algorithm to find local minima of function which is unbounded from below [closed]

I have a differentiable function $\mathbb{R}^n \to \mathbb{R} $ of several variables $f(x_1,...,x_n)$, whose form I can write down and compute derivatives of. Typically $n = 8$. The function is ...
math_lover's user avatar
4 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 ...
Rolf Rolles's user avatar
0 votes
0 answers
18 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, ...
SOFe's user avatar
  • 133
2 votes
1 answer
37 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: ...
wjwrpoyob's user avatar
  • 141
3 votes
1 answer
196 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)$. ...
Jun Yang's user avatar
3 votes
2 answers
64 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) =...
user187240's user avatar
2 votes
1 answer
71 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$, ...
Dan's user avatar
  • 51
0 votes
1 answer
18 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\}...
minnie's user avatar
  • 1
1 vote
1 answer
74 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 ...
MathematicsBeginner's user avatar
-3 votes
1 answer
68 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 ...
proof-of-correctness's user avatar
0 votes
1 answer
41 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 ...
Rohit Pandey's user avatar
2 votes
2 answers
100 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 ...
Daniel García's user avatar
0 votes
1 answer
25 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 ...
kairocks2002's user avatar
1 vote
1 answer
22 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 ...
EXPTIME-complete's user avatar
2 votes
2 answers
105 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 ...
Rohit Pandey's user avatar
4 votes
2 answers
127 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 ...
user2891462's user avatar
2 votes
1 answer
356 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 ...
siminsimin's user avatar
0 votes
0 answers
22 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 ...
synzgrsck's user avatar
0 votes
2 answers
55 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 ...
turtle's user avatar
  • 117
2 votes
1 answer
68 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 ...
essacult's user avatar
0 votes
2 answers
306 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....
XerneraC's user avatar
1 vote
0 answers
28 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), ...
Mark's user avatar
  • 11
3 votes
1 answer
227 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 ...
askyfullofstars's user avatar
0 votes
0 answers
104 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 ...
Li Haoyi's user avatar
1 vote
0 answers
71 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. ...
Dzmitry Lahoda's user avatar
-3 votes
1 answer
70 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 ...
Mark's user avatar
  • 11
2 votes
0 answers
71 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$, ...
Christopher-Lloyd Simon's user avatar
2 votes
1 answer
59 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 ...
F.C. Akhi's user avatar
  • 123
2 votes
0 answers
47 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) = ...
Jürgen Böhm's user avatar
1 vote
1 answer
45 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 ...
J. Schmidt's user avatar
1 vote
0 answers
69 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, ...
zero_day's user avatar
0 votes
3 answers
59 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 ...
HappMacDonald's user avatar
2 votes
0 answers
117 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 ...
F.C. Akhi's user avatar
  • 123
1 vote
0 answers
22 views

CNF Horn-renamability to 3-CNF Horn-renamability reduction?

A CNF formula is Horn-renamable if you can invert variables in such a way that each clause has at most one positive literal. There is an algorithm based on a reduction to 2-SAT given in Renaming a Set ...
rus9384's user avatar
  • 1,654
1 vote
1 answer
88 views

Loop Bounds vs. Iteration Domain in Polyhedral optimization

Context: I was reading a tutorial on polyhedral optimization. But got confused while trying to translate the iteration domain (i.e. loop bound) to set builder notation. Problem Description: A code ...
F.C. Akhi's user avatar
  • 123
1 vote
0 answers
28 views

ensure connectivity in geometric optimization

I am working on parts of my master-thesis and got to a problem which I would like to solve and develop some algorithm for. Basically I am dealing with 2d-geometry which I would like to represent using ...
Finn Eggers's user avatar
0 votes
0 answers
40 views

How to optimally construct queries asking about the class of an object to eventually find it?

Consider the following problem stated formally: You are given $n$ objects $o_1$, $o_2$, ..., $o_n$ and $k$ classes $c_1$, $c_2$, ..., $c_k$, each class containing some objects; an object is chosen. ...
sbh's user avatar
  • 51
1 vote
0 answers
39 views

How do I optimally fuse nodes in a tree structure?

I am trying to solve the following problem. I've tried to find the name of this problem, but could not really find what I was looking for. I assume there should be some graph-theory that covers it, ...
RunOrVeith's user avatar
2 votes
2 answers
357 views

Algorithm that generates verification program from solution program of NP problem

I don't know complexity class theory well so I might make some categorical errors, but I will try to ask this question anyways. Suppose you have written a function in some programming language which ...
Robert Wegner's user avatar
0 votes
1 answer
65 views

Is the square-root sum problem convex?

The square-root sum problem is: given positive integers $a_1,\ldots,a_k$ and $b_1,\ldots,b_k$, decide if $\sum_i \sqrt{a_i} > \sum_i \sqrt{b_i}$. The exact run-time complexity of this problem is an ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
39 views

Buy two chocolates when want MAXIMUM nonegative spend

This is a self-study inspired by the trivial https://leetcode.com/problems/buy-two-chocolates/. Basically the question is as follows: if you have a value of money m ...
JoeTheShmoe's user avatar
1 vote
2 answers
32 views

strip packing problem with fixed x-coordinate

Similar to the classic 2D strip packing problem, we want to put N blocks into a 2d strip and minimize the height of the strip. Each block has to be put at the fixed x-coordinate. The width and height ...
Xiaotian Hu's user avatar
3 votes
1 answer
201 views

is there an efficient algorithm to find the optimal partition of a matrix?

Consider an $n \times n$ matrix of integers. Define a boundary in the matrix to be a sequence of cells, one per x-coordinate, where the y-coordinates of the boundary either stay the same or go up/down ...
Simd's user avatar
  • 996
1 vote
1 answer
75 views

Does $\mathsf{P} = \mathsf{NP}$ imply $\mathsf{PO} = \mathsf{NPO}$?

The class $\mathsf{NPO}$ is defined as optimization problems such that the corresponding decision problems defined with a threshold are in $\mathsf{NP}$. Let $A$ be an optimization problem and $B$ a ...
Nathaniel's user avatar
  • 15.7k
1 vote
0 answers
110 views

What's the name of the genre of algorithms for efficiently collecting common factors?

I'm working with sparse vectors represented as index (array of unsigned integers) and coefficient (array of floats with the same ...
tutizeri's user avatar
  • 139
3 votes
1 answer
28 views

How can I model this optimization problem?

We're looking to model the following problem as a standard optimization problem (or even a non-standard one). We can come close, but nothing seems to fit exactly. We have a working algorithm coded, ...
Ted Hopp's user avatar
  • 133
2 votes
0 answers
117 views

Finding highest value/weight ratio in dependency graph: NP-hard?

I have the following problem, and would like to figure out whether or not it's NP-hard - primarily to know that searching for a polynomial algorithm for it is futile. Approximations are possible, and ...
Pieter Wuille's user avatar
2 votes
1 answer
69 views

Efficient algorithm for finding a vector to maximize the number of positive dot products with a given set (finding the maximum overlap of half-spaces)

I have a large set $\mathbf{V}$ of vectors in $\mathbb{R}^d\setminus\{\mathbf{0}\}$ and need to find a vector $\mathbf{u}$ that maximizes $\sum_{\mathbf{v}\in\mathbf{V}}\mathbf{1}_{\mathbf{u}\cdot\...
multiplywithadot's user avatar
0 votes
0 answers
22 views

Placement of Tasks from Dataflow Graph on a Physical Graph

I have a dataflow graph where a set of different types of tasks are placed in corresponding types of nodes. Say the task types are called A, B, and C. A-type tasks are placed in all the leaf nodes of ...
bsha's user avatar
  • 1
3 votes
2 answers
417 views

Find Minimum Transformation Between Multisets of Lists of Cards

Brief: I have two configurations, a and b, of the same set of Rummikub tiles (a may not be a ...
xdaimon's user avatar
  • 53

1
2 3 4 5
37