Questions tagged [optimization]
Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.
1,411
questions
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{...
5
votes
2answers
2k views
Is Differential Evolution a genetic algorithm?
I am trying to classify the Differential Evolution algorithm according to the framework in the book:
Introduction to Evolutionary Computing
The authors classify the field of evolutionary ...
5
votes
2answers
395 views
Is this an instance of a well-known problem?
Context
I am developing an application and came across a problem that seemed difficult to solve. Before attempting to reinvent the wheel (and trying to solve an NP complete problem on my own), I ...
5
votes
3answers
1k views
How to choose the maximum number of nodes (with constraints) from a graph
Consider a connected undirected acyclic graph $G$ with $n$ nodes and $n-1$ edges. The nodes have non-negative integer weights less than $n$.
A positive integer $x$ is given and you want to choose at ...
5
votes
2answers
62 views
Detecting conservation, loss, or gain in a crafting game with items and recipes
Suppose we're designing a game like Minecraft where we have lots of items $i_1,i_2,...,i_n\in I$ and a bunch of recipes $r_1,r_2,...,r_m\in R$. Recipes are functions $r:(I\times\mathbb{N})^n\...
5
votes
2answers
100 views
Algorithm for choosing unique options with least overall cost
Problem And Question
I am looking for pointers for an efficient algorithm for the following problem.
It is hard to explain without some data so first I will provide some example data:
Destination 1:...
5
votes
1answer
420 views
What is the formal name for this algorithmic problem?
I'm doing some work on a problem and I'm finding it difficult to research it with out the actual name of the problem, since the problem I'm working on gives it it's own abstraction.
The problem is ...
5
votes
2answers
173 views
Constraint violation and efficiency in search
It seems that (in a broad sense) two approaches can be utilized to produce an algorithm for solving various optimization problems:
Start with a feasible solution and expand search until constraints ...
5
votes
2answers
277 views
Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraints
Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or be unbounded below?
Fact 1: For monotone submodular functions, Nemhauser, ...
5
votes
1answer
130 views
Vertex cover problem with 2-element vertices
Let $G = (W, E)$ be an undirected graph, where $W = \{(v_i,v_j) \in V \times V : v_i > v_j\}$ and $E$ is a set of $2$-element subsets of $W$ such that, given two edges $e_1 = (w_1, w_2)$ and $e_2 = ...
5
votes
2answers
354 views
Data structure for sparse matrices for an online problem
I need to compute a large linear optimization problem very often after recieving updates to my optimization problem.
That is I have a linear problem to find an x such that
$x_1 * c_1 + ... + x_n * ...
5
votes
1answer
3k views
Is the set partitioning problem NP-complete?
I know that the set partitioning problem defined like this:
Given $$S = \left\{ x_1, \ldots x_n \right\}$$ find $S_1$ and $S_2$ such that $S_1 \cap S_2 = \emptyset$, $S_1 \cup S_2 = S$ and $\...
5
votes
1answer
577 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 ...
5
votes
1answer
497 views
Heuristic algorithms for the dense assignment problem
Given a dense assignment problem ($n$ tasks assigned to $n$ workers, where each worker can do any one of the tasks), I understand the best complexity is $O(n^3)$, using the Hungarian Algorithm or ...
5
votes
1answer
552 views
Distance k-Dominating Set on a Tree
I don't consider myself very good at math, but nevertheless I enjoy solving optimization problems like the ones often asked in ACM ICPC (a college programming competition). I recently came across an ...
5
votes
2answers
3k views
Optimization problem vs decision problem - reduction
Assume we have an optimization problem with function $f$ to maximize.
Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
5
votes
1answer
2k views
Weighted subset sum problem
Given an integer sequence $\{ a_1, a_2, \ldots, a_N \}$ that has length $N$ and a fixed integer $M\leq N$, the problem is to find a subset $A =\{i_1, \dots, i_M\} \subseteq [N]$ with $1 \leq i_1 \lt ...
5
votes
1answer
1k views
Optimizing a strictly monotone function
I am looking for algorithms to optimize a strictly monotonic function $f$ such that $f(x) < y$
$f : [a,b] \longrightarrow [c,d]
\qquad \text{where } [a,b] \subset {\mathbb N}, [c,d] \subset {\...
5
votes
1answer
260 views
Can I prove that I have x such that f(x) < c without revealing x?
I'm interested in applications to verifiable computing. Let's say Alice would like to find an x such that f(x) < c for some real-valued function f and some c of Alice's choosing, so she hires Bob ...
5
votes
1answer
243 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\}$,...
5
votes
1answer
165 views
Optimization over convex combinations in a circle
Consider the following situation: given a triangle $ABC$ inscribed in a circle, define $f$ as the product
$$f(P) = d(P, A) \; d(P,B) \; d(P,C)$$
where $P$ is a point on the circle and $d$ are ...
5
votes
1answer
171 views
Find ellipsoid that contains intersection of an ellipsoid and a hyperplane
I have an $n$-dimensional ellipsoid $E$ and a hyperplane $H$. This hyperplane cuts $E$ into two parts: $E_1$ and $E_2$ (whose disjoint union is $E$). I want to find another ellipsoid $E'$ that has ...
5
votes
1answer
91 views
Finding minimal and complete test sets for circuits
I have been playing around with analysis of circuits and am trying to generate test vectors. In order to exercise the circuit in the manner I require, I need a vector that includes every change in the ...
5
votes
1answer
234 views
Algorithms for logical synthesis of multiple output bits?
Karnaugh maps and the QuineāMcCluskey algorithm can be good choices for coming up with fairly minimal logical expressions that match the requirements of a truth table.
What if I have a situation ...
5
votes
1answer
156 views
Fast solution for a combinatorial maximizaton problem
You are given a natural number n (n<20). We construct the set S from all binary numbers with n bits. We call two numbers "compatible" if they don't have any common substring of length n-1 (...
5
votes
1answer
658 views
Finding set of disjoint sets with additional value optimization
I've got a set $Q$ of pairs $[S, v]$ where $S$ is a nonempty set and $v$ is a value ($v \in \mathbb{N}_{+}$). I need to find a subset $R$ of $Q$ with following properties:
Sum of all $v$'s is maximum
...
5
votes
1answer
3k views
Seating Chart Optimization
I'm trying to find an algorithm to solve the seating chart problem. The goal is to place pepole at one (or multiple) tables such that the overall happiness is maximized.
Each seat has neighbors. A ...
5
votes
1answer
111 views
Find a strategy to evade hungry lions on the real line for the longest time
This is an interview question I was asked, which I don't know how to approach. I would appreciate pointers to algorithms I should look up.
You are placed on the real line, and there also are $K$ ...
5
votes
2answers
2k views
Finding k-nearest neighbors to a set of nodes in a large graph
Given a large graph $G=(V,E)$, a set of nodes $S\subseteq V$, the problem is finding the $k$-nearest nodes in $V$ to the nodes in $S$.
Given a pair of nodes $(u,v)$, the distance $d(u,v)$ between $u$ ...
5
votes
2answers
593 views
Approximate subset sum with two-dimensional vectors
Consider the following optimization problem:
Given $n\leq 10^3$ vectors $v_i\in\mathbb{R}^2$, all of which are small, i.e., $\|v_i\| \leq 1$, find a subset $S$ of them that minimizes
$ \| w + \...
5
votes
1answer
1k views
How can I restructure matrices to have non-zero elements close to the diagonal?
I have a matrix $C \in \mathbb{N}^{n \times n}$. Semantically, it is a confusion matrix where the element $c_{ij}$ denotes how often members of class $i$ are predicted by a given classifier as members ...
5
votes
1answer
41 views
Find expression with minimal distance to target
I will start of with an informal example and give a more formal problem definition later.
Say I have a finite set of positive real values: $\{2.3, \pi, 4.382, 0.3\}$. Using normal addition and ...
5
votes
1answer
369 views
Transition coverage for a DFA
Let $G$ be a directed graph, with a single source node $s$. I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where ...
5
votes
1answer
884 views
Decision vs Optimization version for Problems of two Parameters
Let's say I have an optimization problem called $k$-foo which asks for a solution of size $k$ minimizing some quality criterion.
Now the corresponding decision problem $foo(M)$ would be: Is there a ...
5
votes
3answers
2k views
Min cost max flow in bipartite run time
I have a bipartite graph with $|E|=O(|V|^2)$, a super-source and a super-sink. I am looking for the min-cost max-flow (the max-flow of all possible max-flows that has the minimum cost).
For the sake ...
5
votes
1answer
69 views
Maximize area of light with 4 light sources on a diagram of a room
Given a diagram of a room with obstacles in it (like walls or furniture), find the 4 best places to put omnidirectional light sources in it so the area that is lighted is maximized.
Here is a simple ...
5
votes
1answer
65 views
Minimizing $\sum_{i=1}^n x_i/y_i$ over a polytope
I want to solve a linear programming problem in the $2n$ variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ where the cost is of the form $x_1/y_1 + \cdots + x_n/y_n$. Specifically, I want to solve
\...
5
votes
1answer
295 views
Maximize product of sum of two subset
Given two sets $A = \{a_1, a_2, \dots, a_n\}$ and $B = \{b_1, b_2, \dots, b_n\}$, both consist of positive numbers, this problem is to find a subset $S$ in $\{1, 2, \dots, n\}$ to maximize
$$
\left(\...
5
votes
1answer
97 views
Location Selection Algorithm in Solar Engineering
This is a practical problem in energy generation with heliostats.
We have a number of heliostats basically forming the shape of a doughnut. The facility needs to deploy hubs on those heliostats. One ...
5
votes
2answers
196 views
What data structure might this game use?
This question is not about game development or about actual implementation details.
I was playing Little Alchemy yesterday. (Warning: Productivity hazard.) You start with the four classical ...
5
votes
1answer
96 views
Coercing a list of nodes into the most probable tree
Suppose that we have an RTF document which contains sections and sub-sections. The sections and subsections all have headings that are visually marked up (e.g., bold and italic), but the document ...
5
votes
1answer
82 views
Complexity of covering subset of the monoid $(\{0,1\}^n, \text{OR})$
(At the very bottom of this, I will shortly describe the motivation for this question.)
Assume we have a commutative monoid $(G,\circ)$, i.e. a set $G$ with a commutative binary operation $\circ$ ...
5
votes
2answers
81 views
Global Optimization of a well-defined function with gradient information
I try to minimize the function
$$ f(x_1, ā¦x_n)=\sum\limits_{i}^n-a_i\cos(4(x_i-b_i)) +\sum\limits_{ij}^\text{edge}- \cos(4(x_i-x_j)), \quad
x_i,b_i\in (-\pi, \pi)$$
where $\sum\limits_{ij}^{edge}$ ...
5
votes
2answers
329 views
How can I efficiently find the optimal order to apply special offers to a shopping cart?
Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
5
votes
1answer
2k views
Variation of Set Cover Problem: Finding a maximum-sized collection of disjoint set-covers
I have the following problem, which seems to be similar to Set Cover.
We are given a set $U$ of elements (the universe, e.g., $U=\{1,2,3,4,5\}$).
We're also given a set $S$ of subsets (e.g., $S=\{\{1\...
5
votes
1answer
699 views
Dividing a weighted planar graph into $k$ subgraphs with balanced weight
I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge ...
5
votes
0answers
93 views
Specific quadratic 0-1 knapsack problem solvable in linear time?
I am interested in a simple variant of the quadratic knapsack problem.
Let $\{w_1, \ldots, w_n\} \in \{0,1\}$ be $n$ weights and $\{v_1, \ldots, v_n\} \in \mathbb{R}$ be $n$ values. Furthermore, ...
5
votes
0answers
182 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 ...
5
votes
0answers
144 views
Approximate Weighted Partial Max SAT
Given a Weighted Partial Max SAT problem (WPM-SAT) - are there generally used algorithms or techniques to generate 'approximate' solutions, which are
not necessarily optimal, but found faster than ...
5
votes
0answers
437 views
How to apply ant colony optimization to the TSP but repeating nodes and edges
I'm learning the Ant Colony Optimization Algorithm and I would like to apply it to a variation of the TSP problem (find the path that start from a node, crosses all nodes and finish in the initial ...
