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
1answer
54 views

Compute unknown matrices that minimize a sum

This problem is about working with smart-phone accelerometers. To calibrate accelerometer, I need to find three unknown matrices T, K and B that minimize this sum: $$\sum_{i=0}^N(|g|^2 - |TK(a_i + B)|...
2
votes
3answers
4k views

Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
3
votes
3answers
170 views

Minimal number of nodes needed to connect a disconnected graph

Given a graph $G = (V, E)$ with $V = U \uplus T$ (let's say the vertices are labelled $U$ or $T$), I am looking for the smallest set $U' \subseteq U$ such that $G[U' \cup T]$ is connected. If we ...
5
votes
1answer
545 views

Maximizing the sum of selected elements in a matrix

I’m trying to find an efficient algorithm for the following optimization problem: Given a matrix $A$ with elements $a_{ij}$ and dimension $k$, select exactly $n$ elements from $A$ ($n<k$) such ...
3
votes
1answer
51 views

Minimum number of moves required to transfer items from source bins to target bins?

I have a set of source bins, each with some number of items, and a set of target bins. I want to move all of the items from the source bins to the target bins, using the minimum number of moves. ...
1
vote
1answer
491 views

stable marriage/residency problem with multiple matches

Consider the stable marriage problem, where both sides want to match with multiple individuals from the other side (perhaps a fixed number, or perhaps within some range). Something like, if doctors ...
1
vote
0answers
42 views

Re-arrangement Algorithm Minimizing Total movement

I have $n$ items arranged on a straight line (like a number line, items can only move 2 directions). The each item has a size, some distance around their center position, that can't overlap with ...
2
votes
1answer
166 views

Maximum connected cell length containing two different numbers

Suppose we are given an $n\times m$ matrix $M$ of positive integers. The adjacent cells of a particular cell is the up, down, left and right cells. Like for cell $M[i][j]$ the adjacent cells are $M[i-...
1
vote
1answer
38 views

How many queries does it take to find the best flight?

I often find flights through a search engine like Google Flights. On input some refined subset of the space of all flights (e.g., non-stop only, departing in the morning, from one of two airports, and ...
2
votes
1answer
15 views

Strassen's algorithm on unit vectors?

I am trying to do a dot product of two vectors of each 128 dimension. I am just looping each member and calculating the sum. ...
5
votes
0answers
173 views

Can all types of problems be converted to decision problems?

We know all optimisation problems can be converted to decision problems. Is that true for search problems, counting problems and function problems as well? Description of the types of problems is ...
0
votes
0answers
14 views

Optimizing convex function in an online manner

I have a convex function of $n$ variables, $f(x_1,x_2,\dots,x_n)$ and need to find its minimizer. Are there algorithms that can retrieve the minimizer in an online fashion? i.e. solve for $x_1^{(opt)}$...
2
votes
2answers
260 views

Implications of Integral linear program

Let $(P)$ an Integer Linear Program, where we aim to find $x\in \{0,1\}^n$ maximizing a linear function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ under some linear constraints $Ax\le b$ Let $(P^*)$ be ...
1
vote
1answer
2k views

Find all local minima in a big 2d array

Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all ...
0
votes
0answers
178 views

Shortest path between 2 nodes subject to constraints

I am trying to find shortest path between 2 nodes in a graph similar to below: Each edge has a weight assigned to it. Also, the graph is directional with each edge directing from left to right. I ...
1
vote
0answers
27 views

Markov Decision Process Optimal Policy

Consider the setting of finite MDPs. I will be using the notation in Chapter 2 of http://rll.berkeley.edu/deeprlcourse/docs/ng-thesis.pdf. Say we have already computed values for the optimal $Q$-...
2
votes
1answer
80 views

Find the nearest sum to a given number of two elements in sorted matrix

Given a sorted $n\times n$ matrix $A$ of real values. That is $a_{ki}<a_{kj}$ and $a_{it}<a_{jt}$, when $i<j$. Propose and algorithm, finding two elements of this matrix with the sum nearest ...
1
vote
1answer
72 views

video shape recognition in real time

I believe from common sense that video shape recognition problems (identifying shape of a moving object) is of natural interest in many real world situations. The process of identifying is understood ...
0
votes
1answer
23 views

Evolutionary algorithm - is there a relation between minimum iterations and size of decision variables

I am solving an optimization problem using SPEA2, my problem has three cases with decision variables 25, 50 and 100 in each case. I want to ask if there is some relationship between the number of ...
2
votes
1answer
155 views

Find the sum of the first K subsets of integer array

We have given a multiset of $N$ integer, both positive or negative. Consider all $2^N$ subsets, sorted by their sum (the empty subset has sum 0). We want an algorithm that outputs only the first $K$ ...
0
votes
1answer
57 views

Alternatives to evolutionary computing for structure, design and policy optimization (optimal structure search)?

I once had this question https://math.stackexchange.com/questions/1083338/structural-design-meta-optimization-is-there-mathematical-theory-optimiza about the methods for finding optimal structures, ...
1
vote
1answer
223 views

Assuming that P=NP - Finding an optimal algorithm for 3SAT

Let assume that P=NP so we have both search and decision algorithms for 3SAT at polynomial time. Can you help me to find an optimal algorithm for optimize 3SAT, i.e.: to find the maximum number of ...
5
votes
4answers
613 views

Are there any optimization problems in P whose decision version is hard?

Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any ...
1
vote
0answers
47 views

Polynomial time algorithm for a simple machine scheduling problem

Think about a setting where there are $n$ tasks and $m$ machines. We are interested in task-machine assignment. Let $p_i$ be a non-negative completion time of job $i$. Also, $x_i$ denotes the machine ...
0
votes
1answer
130 views

Maximize vertex cover weights with bounded edge weights in a connected subgraph

Similar questions were asked elsewhere, but no satisfying answers occurred yet. In a graph with weights for both vertices and edges, I want to find a subgraph, whose sum of internal edge weights is ...
1
vote
0answers
103 views

Chromosome length in Genetic Algorithms

In order to find the appropriate length of chromosomes in GA programming, the author of this book states: Suppose six decimal places for the variables' values is desirable. It is clear that to ...
3
votes
0answers
469 views

Understanding the Polyhedral Model

I am wondering at a high level the mathematics of the Polyhedral Model. The polyhedral model (also called the polytope method) is a mathematical framework for programs that perform large numbers of ...
1
vote
1answer
56 views

Has the problem of finding the most profitable transactions given a set of discrete time series been well-studied?

Overview and Problem Description Suppose I have a set of N discrete time-series (represented as a map from time-interval-index to value/utility), and I would like to identify a sequence of actions in ...
0
votes
1answer
31 views

The optimal way to find leaves in a weighted full binary tree

Let T be a full binary weighted tree. For a node v in T, the cost of going right is a i.e w(v, v.right) = a while w(v, v.left) = b How do I find optimal paths to all leaves from the root. I don't ...
0
votes
0answers
29 views

How many optimal alignments can be there for a string of length m with a string of length n?

So I was practicing optimal alignment algorithm and I was stuck with this question of finding optimal alignment for a string of length m with a string length n ? Also is it possible to run it in theta(...
1
vote
0answers
59 views

Spanning tree with equally separated edge weights

I have a fully-connected graph $G=(V,E)$ with edge weights $w(v)\in\mathbb{R};v\in V$ and I need to find a spanning tree $T=(V_t\subseteq V,E_t\subseteq E)$ where the set of edge weights in the tree ...
0
votes
1answer
73 views

Choose minimum subset of edges in tree that connects all important nodes

Let's say we have given weighted tree of size $n$ and list of important nodes in the tree $k$. We want to choose subset of edges of the tree such that: For each two important nodes at least one edge ...
2
votes
1answer
23 views

Following but not intersecting time segments to detect multiple accounts

In some code I'm currently writing, I'm stuck on the following algorithm to implement. The goal is to find real world users using multiple different accounts. I've a List of UserData. This list is ...
2
votes
1answer
42 views

Methods, Routines, or Algorithms To Optimize Selection of String Compression Methods

When encoding a a 2D Datamatrix barcode, I want the smallest output size. There are means to encode a compressed a string using some methods like C40. Reference: Here's a reference: https://en....
1
vote
1answer
217 views

Minimum cost to convert one array to another

Given two arrays $A$ and $B$ of integers, both of size $N$, such that for all $0 \le i \le N-1$, $A[i] \ge B[i]$, we have to convert array $A$ to array $B$. For this we can do only one type of ...
0
votes
0answers
76 views

Optimise 1D cutting stock problem - maximum waste that can be removed with n cuts

The problem statement can be made as follows. There is a 1D length of raw material that contains "net" and "waste" intervals. Using 2n cuts, sections of material can be removed so that less waste has ...
3
votes
1answer
344 views

Minimal date interval cover algorithm

The problem involves date intervals filtered by days of week. For example, the filtered interval {2001 APR 1 - 2001 APR 30, 17} corresponds to all Mondays and Sundays between April 1 and April 30. ...
1
vote
0answers
76 views

Are there Dynamic programming speedups for $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$

I am wondering if there are dynamic programming speedups for the minimization problem $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$. Now I understand that its highly unlikely that such thing would exist for ...
1
vote
1answer
266 views

Travelling salesman problem with small edge weights

Are there any advantages in finding the shortest tour for the problem if edge weights are much smaller than the number of vertices? Let's say the maximum edge weight is $n$, and the number of ...
1
vote
1answer
56 views

Best set of orders

I have the ambition to build an application that determents the best set of orders. Let's say I'm an postage-stamp collector. And I have certain postage-stamps on my wish list. On the secondhand-...
0
votes
0answers
47 views

Linear Programming if-then-else [duplicate]

I have a binary variable $y\ \epsilon\ \{0,1\} $ and a real $x$ which has the following boundaries $-100\leq\ x \leq\ 100$. How can I reformulate the following statement: $$ y = \begin{cases} 0 & ...
0
votes
0answers
51 views

Finding k points in a set with largest total distance (measured to nearest point in k)

We are given a set of points $S$. Given $K$ is any subset of size $k$, how do I efficiently find the following: $\mathop{\arg\max}\limits_K$ $\sum_{x_i\in K} \mathop{\min}\limits_{x_j \in K, x_j \ne ...
5
votes
1answer
1k views

The Entropy of the phrase “Eile Mit Weile”

I want to calculate the Entropy of the phrase "Eile mit Weile". I found the probability of each letter as the following $$P(e)=\frac{4}{12}$$ $$P(i)=\frac{3}{12}$$ $$P(l)=\frac{2}{12}$$ $$P(m)=\frac{...
1
vote
1answer
130 views

Minimum path cover— Disjointed paths with minimum total number of edges

Let $T=(\mathcal{V},\mathcal{E})$ be an udirected acyclic graph and $|\mathcal{V}|=n$. Let $\mathcal{V'}$ be $\mathcal{V'}\subset \mathcal{V}$ where $|\mathcal{V'}|=2m\leq n$. There are $2m \choose 2$ ...
2
votes
1answer
389 views

Interval scheduling problem with priorities

I have a problem that is similar to the interval scheduling algorithm but it involves priorities. My data sets consist of the following data: Cars with the start and end time of parking, along with ...
1
vote
1answer
69 views

Minimum capacity cut reduction from digraph with two edge weight sets

Given a digraph $G$ and $f, g : E(G) \mapsto \mathbb{R}$, how would you find a cut $(X,\bar{X})$ with $s \in X$ and $t \in \bar{X}$ such that $\sum_{e \in \delta^+(X)}{f(e)} - \sum_{e \in \delta^-(X)}{...
0
votes
1answer
65 views

Intuitive way to understand “Run-Length Encoding”

Run-Length Encoding is the simple form of lossless data compression in which compression in which runs (execution) of data are stored as a single data value and count rather than as the original run (...
0
votes
1answer
45 views

Minimizing $\max | x_i - \mu |$

How can we construct an algorithm which finds $\mu$ that minimizes $\max | x_i - \mu |$ in a linear time for an array of numbers $[x_1, x_2, \ldots, x_n]$? I take $g = \max_{i\in \{1,\ldots,n \} } ...
1
vote
2answers
1k views

Is global non-convex optimization NP-complete?

Assume I have some non-convex function $f(x_1, x_2, ...)$ and I want to optimize it to find a global minimum. I feel like it is easy to show that this problem is in the class NP with the decision ...
2
votes
1answer
42 views

Finding the maximum of a random forest

If we have some collection of decision trees with single-variable splits and a constant value at each leaf node, the average over all trees gives some function from $\mathbb{R}^n \to \mathbb{R}$. Is ...

1
7 8
9
10 11
28