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
1
vote
0answers
45 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
108 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
90 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 ...
2
votes
0answers
341 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
50 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
26 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
28 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
53 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
62 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
38 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
162 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
63 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
294 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
74 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
226 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
53 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
49 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
98 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
360 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
62 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
62 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
44 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 ...
2
votes
1answer
94 views

Local search (Hill Climbing) scope and definition

I'm taking an artificial intelligence class and in one of the recent lectures the topic was local search algorithms, more specifically Hill Climbing. At one point the professor showed the classic 8-...
1
vote
1answer
1k views

Using 2-opt Heuristic in a Genetic Algorithm for TSP

I read few papers while trying to find some better approachs to solve the TSP (Traveling salesman problem) as close to the optimal solution as possible. I implemented a Improved Greedy Crossover (...
1
vote
0answers
66 views

Appropriate algorithm or heuristic for task scheduling

I'm sure this problem has been addressed before, but I'm unable to find an exact description of it. I have $m$ machines, and $n$ tasks that need processing. Each task takes a variable amount of ...
1
vote
1answer
35 views

How to find an arrangement of a sequence that has the lowest cost

Given is a set of $n$ items: $x_1, x_2\ldots, x_n$. Additionally, we have a non-symmetrical evaluation function $f(x_i, x_j)$ that gives a cost value of two items. Note that $f(x_i, x_j)\neq f(x_j, ...
2
votes
1answer
143 views

Topological sorting and NP-hard proof

I meet a problem. I can find a sub-optimal solution, but cannot find an optimal one and cannot prove its NPC hardness. The problem can also be described as follows. Given a sequence $X=\{x_1,x_2,...,...
1
vote
1answer
29 views

TSP when cost depends only on location in sequence

I want to change the original TSP problem as follows: the cost to visit a city is not related to the previous city that it visited just now, but only on its position in the sequence. Is the problem of ...
0
votes
1answer
24 views

How to extract a set $C$ that contains $N$ subsets of a set $B$, covers all elements of an external set $A$, but $N$ is minimal?

Let $A$ denote a set that contains a relatively large number of different strings. Let $S_i$ denote these strings. Let $B$ denote a set of sets such that each subset contains a (relatively small, ...
0
votes
1answer
23 views

In two sets, identify set of pairs with maximal sum of connections

Given two sets of items $A = { a_1, .., a_N }, B = { b_1, .., b_M },$ and assuming a connection weight $w{_i}_j \ge 0$ between any possible pair $(a_i, b_j)$ that contains one item of each set, how ...
5
votes
1answer
237 views

Moving an edge in a weighted tree to maximize longest path length

Let $G$ be a undirected edge-weighted tree, where all edge weights are positive. A move of an edge $\{u,v\} \in E(G)$ is the operation of deletion of $\{u,v\}$ and the addition of a new edge $\{x,y\}$,...
3
votes
1answer
1k views

Why is integer programming more difficult than (real) linear programming? [duplicate]

Why is integer programming (IP) more difficult than (real) linear programming (LP)? I searched a lot on the web, but I didn't find an answer.
1
vote
2answers
259 views

ILP runtime seems to be linear?

I have a variation the shortest path problem, formulated as an ILP. The system model is as follows: There is a connected digraph consisting of 20 nodes, with each link having an associated weight ...
0
votes
0answers
21 views

What are the reasons behind using constraints in convex optimization?

We use the following notation to describe a minimum convex optimization problem: ...
1
vote
0answers
217 views

solving max cut problem on a huge graph (500 x 500) using Semidefinite Programming with CVXOPT

So I am learning to do SDP relaxation on graph problems, and for this max cut problem I am given a 500*500 graph, and I am using the straightforward relaxation. $W$ is the weight matrix, $X = u u^T$ ...
2
votes
1answer
89 views

Filling a string with wildcards with minimum cost

You are given a string with wildcards, e.g. X***Y*Z. Your goal is to print an input string filling all the wildcards in the given string. You are allowed to write data to the string in blocks of ...
0
votes
0answers
64 views

Is it possible to make data structure that will find MEX and support modification queries

Let's say we have given array of $n$ elements, now we want to create data structure that will allow us to get the MEX of its elements, MEX meaning the smallest positive integer that is not present in ...
0
votes
1answer
27 views

Multi-type max-flow

Suppose you have $m $ sources $s_i$ and $n $ sinks $t_j$, but every source produces a certain type of flow, out of $k $ types, and every sink demands a certain type as well. We would like to know if ...
6
votes
1answer
2k views

Fitting different rectangles inside a rectangle

I have a fixed rectangle of size X x Y. I also have a bunch of rectangles of different sizes. I want to check if these rectangles can fit in the larger X x Y rectangles knowing that one can rotate ...
4
votes
2answers
62 views

Among $k$ unit vectors, find odd set with sum length less than 1

I have $k$ unit vectors in $\mathbb{R}^k$. Can I efficiently identify a set of $2n+1$ vectors $v_1, \dots v_{2n+1}$ such that $\sum_{i< j} v_i\cdot v_j < -n$ for any $n$ -- or determine that no ...
1
vote
1answer
60 views

Portfolio allocation with a few twists

A similar question has been asked here, but this one is more complicated and has more constraints. I'm trying to find an algorithm to solve the following (real-life) problem: A customer has $M$ ...
2
votes
0answers
29 views

Filling a board with maximum number of fixed size tiles

You are given a rectangular board of known size, e.g. 20x20 cm. Some 1x1 cm pieces are missing. Your task is to cover this board with a maximum number of 2x2 cm tiles (an example is attached below), ...
1
vote
1answer
63 views

What do we call a greedy algorithm that tracks the best $n > 1$ solutions?

A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima. To avoid this problem, we may keep track of the best $n > 1$ ...
1
vote
0answers
52 views

Unknown length of chromosone in genetic algorithm

I've read some about genetic algorithms and the general approach, but I haven't found anything about using it when the length of the solution is unknown. How would the generation of the initial ...
-1
votes
1answer
43 views

Global optimization algorithm based on MapReduce

In the field of the intelligent swarm, there are many algorithms can find global optimization, such as Ant Colony Optimization (ACO), particle swarm optimization (PSO). Is there any optimization ...