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
9
votes
6answers
3k views

Are there variations of the regular runtimes of the Big-O-Notation?

There are multiple $O$-Notations, like $O(n)$ or $O(n^2)$ and so on. I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log n^2)$, or if those are mathematically ...
9
votes
2answers
11k views

Branch and Bound explanation

I have a test about the branch and bound algorithm. I understand theoretically how this algorithm works but I couldn't find examples that illustrates how this algorithm can be implemented practically. ...
9
votes
3answers
1k views

How to solve an arrangement problem at the Archive Nationale of France using graph theory?

Good evening! I'm actually doing an internship at the Archives Nationales of France and I encountered a situation I wanted to solve using graphs... I. The dusty situation We want to optimize the ...
9
votes
2answers
175 views

Find an optimal ordering

I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated! Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k} $, for example, ...
9
votes
1answer
525 views

Can we find k shortest paths between all pairs faster than solving the pairwise problem repeatedly?

I want to produce $k$ shortest path ($k$ would be less than 10) between all pairs in a graph. The graph is (actually a subway map): positively weighted undirected sparse with about 100 nodes My ...
9
votes
1answer
157 views

Heaviest planar subgraph

Consider the following problem. Given: A complete graph with real non-negative weights on the edges. Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.) ...
9
votes
1answer
269 views

How to maximize $(h[j]-h[i])(j-i)$ in $O(n)$

I see many algorithmic problems that always reduce to something a long the lines of: You have an integer array $h[1..n]\geq 0$, you need to find $i,j$ such that maximizes $(h[j]-h[i])(j-i)$ in $O(n)$ ...
9
votes
1answer
187 views

Fixed-length decision-tree-like feature selection to minimize average search performance

I have a complex query $Q$ used to search a dataset $S$ to find $H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$. Each query takes on average time $t$ so the overall time in the linear ...
9
votes
0answers
179 views

How to solve the loan graph problem

The problem A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...
9
votes
1answer
3k views

Finding the longest repeating subsequence

Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
8
votes
3answers
3k views

What is the intuition on why the longest path problem does not have optimal substructure?

I was learning about longest paths and came across the fact that longest paths in general graphs is not solvable by dynamic programming because the problem lacked optimal substructure (which I think ...
8
votes
2answers
1k views

Known facets of the Travelling Salesman Problem polytope

For the branch-and-cut method, it is essential to know many facets of the polytopes generated by the problem. However, it is currently one of the hardest problems to actually calculate all facets of ...
8
votes
3answers
576 views

What is the name of this logistic variant of TSP?

I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the ...
8
votes
1answer
494 views

Is there an algorithm for algorithms time/space complexity optimisation?

In 1950s a number of methods for circuit minimization for Boolean functions have been invented. Is there an extension of those methods or anything similar for optimising time or space complexity of ...
8
votes
2answers
773 views

Find the smallest summed distances by uniquely pairing elements of one set to elements of another set

As input I have two sets of points in RN, typically for large N, for example N=40. Supose both sets have m elements: S = s1 ... sm T = t1 ... tm Semantically both sets are equal, but due to noise (...
8
votes
2answers
7k views

Algorithm to find optimal currency denominations

Mark lives in a tiny country populated by people who tend to over-think things. One day, the king of the country decides to redesign the country's currency to make giving change more efficient. The ...
8
votes
2answers
560 views

Minimizing the total variation of a sequence of discrete choices

My setup is something like this: I have a sequence of sets of integers $C_i (1\leq i\leq n)$, with $|C_i|$ relatively small - on the order of four or five items for all $i$. I want to choose a ...
8
votes
1answer
827 views

Linear time algorithm for finding $k$ shortest paths from $s$ to $t$

Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the length of ...
8
votes
1answer
5k views

Quality LISP/Scheme compilers to compete with C/C++

Theoretically speaking, is it possible to have a Lisp/Scheme compiler that can produce code that can compete with compiled C, let's say within 15-25% margin? In my testing, I've found that the ...
8
votes
2answers
2k views

Real world applications for Steiner Tree Problem?

Are there real-world applications of the Steiner Tree Problem (STP)? I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that ...
8
votes
1answer
569 views

Finding the largest 3-clique-free induced subgraph

Consider this problem: Given an undirected graph $G = (V, E)$, find $G' = (V', E')$ such that: $G'$ is an induced subgraph of $G$ $G'$ has no 3-cliques $|V'|$ is maximal So the ...
8
votes
1answer
245 views

How to minimize the cardinality of a set and disjoint partitions subject to constraints in polynomial time?

The real problem I am facing is the following. INSTANCE: I have sets $N:=\{1,\ldots,n\}$ and $K:=\{1,\ldots,k\}$ and matrix $a_{ij}>0$ for all $i\in K$ and $j\in N$. QUESTION: I need to find a ...
8
votes
2answers
601 views

Finding a set of maximally different solutions using linear programming or other optimization technique

Traditionally, linear programming is used to find the one optimal solution to a set of constraints, variables and a goal (all described as linear relationships). Sometimes, when the objective is ...
8
votes
1answer
220 views

Maximum Stacking Height Problem

Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it? Problem ("Maximum Stacking Height Problem") Given $n$ polygons, find their stable, ...
8
votes
0answers
805 views

Find set of points with maximum distance inside given intervals?

Let $A$ be a set of $n$ closed intervals, $I_i$, with both extremes positive integers. Is there an efficient algorithm to find a set of $n$ points $P_i$, with $P_i \in I_i$, such that the minimum ...
8
votes
0answers
608 views

Chained operations on sequences with two operators

Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation? Can we learn from matrix chain multiplication? A generalization of matrix chain ...
8
votes
0answers
179 views

Optimizing order of graph reduction to minimize memory usage

Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used. That is, given ...
7
votes
2answers
4k views

What is the no free lunch theorem?

I've been reading about the No Free Lunch Theorem, but I can't quite understand what it is about. I've heard this theorem described elsewhere as the claim that "no general purpose universal optimiser ...
7
votes
2answers
9k views

How to avoid getting stuck on local optimum, for genetic algorithms

I'm programming a genetic algorithm using grammatical evolution. My problem is that I reach local optimal values (premature convergence) and when that happens, I don't know what to do. I'm thinking ...
7
votes
1answer
247 views

Is weighted XOR-SAT NP-hard?

Given $n$ boolean variables $x_1,\ldots,x_n$ each of which is assigned a positive cost $c_1,\ldots,c_n\in\mathbb{Z}_{>0}$ and a boolean function $f$ on these variables given in the form $$f(x_1,\...
7
votes
2answers
625 views

Finding a fixed-size set whose members are contained by the largest number of other sets

I've been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to ...
7
votes
1answer
1k views

How to implement the details of shotgun hill climbing to make it effective?

I am currently working on a solution to a problem for which (after a bit of research) the use of a hill climbing, and more specificly a shotgun (or random-restart) hill climbing algorithmic idea seems ...
7
votes
2answers
243 views

Are monoids useful in optimization?

Many common operations are monoids. Haskell has leveraged this observation to make many higher-order functions more generic (Foldable being one example). There is ...
7
votes
2answers
156 views

Simplified Maximum Diversity Problem

The Maximum Diversity Problem calls for choosing $m$ items from a list of $n$ items, such that the diversity defined as some metric distance between items is maximized. I have a simpler problem, ...
7
votes
1answer
2k views

How to find the shortest path from some vertex in set $S$ to set $S'$

If i have a graph $G=(V,E)$, a subset of vertices $S \subset V$ and a second set of vertices $S' \subset (V\setminus S)$, what is the best way to find the shortest path connecting the two sets? That ...
7
votes
3answers
13k views

How does the 3-opt algorithm for TSP work?

I understand that the 3-Opt Heuristic for solving the Traveling Salesman problem involves removing three edges from a graph and adding three more to recomplete the tour. However, I've seen many papers ...
7
votes
1answer
146 views

Branch and bound for minimum linear arrangement

I am trying to solve this branch and bound problem but I could not come up with any approximate cost function which is better than the cost. Let's say $G$ is a graph of $n$ nodes $\{1, 2, 3, \ldots , ...
7
votes
3answers
865 views

Algorithm: Finding shortest path through a dungeon in a game

Background I was playing the PC-Game "Darkest Dungeon" recently. In the game, you have to explore dungeons, which consist of connected rooms as shown in the picture below. Here are the rules: You ...
7
votes
1answer
1k views

NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?

I have seen some problems that are NP-hard but polynomially solvable in fixed dimension. Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer ...
7
votes
1answer
221 views

Given 2 sets of n points: minimize sum of traveled distances

I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean ...
7
votes
1answer
166 views

Sorting an unordered pile of items into drawers with minimal drawer movements

A while ago, I was doing my laundry late at night. When I brought my laundry back to my dorm, I started to put it away. My wardrobe is set up as follows: My drawers are categorized by the type of ...
7
votes
1answer
337 views

In s-t directed graph, how to find many small cuts?

Solving the maximum flow problem yields one qualified minimal cut. But I want several (maybe hundreds) small cuts as candidates. The cuts don't have to be minimum cuts, as long as they are small (in ...
7
votes
1answer
3k views

BFGS vs L-BFGS — how different are they really?

I am trying to implement an optimization procedure in Python using BFGS and L-BFGS in Python, and I am getting surprisingly different results in the two cases. L-BFGS converges to the proper minimum ...
7
votes
1answer
258 views

Are coevolutionary “Free Lunches” really free lunches?

In their paper "Coevolutionary Free Lunches" David Wolpert and William Macready describe a set of exceptions to the No Free Lunch theorems they proved in an earlier paper. The exceptions involve two-...
7
votes
1answer
160 views

Hardness of a constrained quadratic maximization

Consider the following quadratic maximization: \begin{align} \max_{\mathbf{x} \in \mathcal{X}} &\quad\mathbf{x}^{T}\mathbf{A}\mathbf{x} \end{align} with \begin{align} \mathcal{X} = \lbrace \mathbf{...
7
votes
1answer
2k views

Greedy strategy for computing the minimum number of rays that hit all balloons

The minimum zap problem below is Exercise 11 in Jeff Erickson's lecture on "Greedy Algorithm". The minimum zap problem can be stated more formally as follows. Given a set $C$ of $n$ circles in the ...
7
votes
1answer
261 views

The heaviest induced subgraph problem

I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w_v: V \mapsto R$, and $w_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ ...
7
votes
0answers
178 views

Algorithms for curve construction

I am interested in algorithms that construct continuous curves between two points in such a way that minimizes an energy functional of the curve. What sort of algorithms are most used for such tasks? ...
7
votes
0answers
153 views

Overlap Maximization problem

Here's the problem: I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
6
votes
2answers
142 views

Which algorithm can I use to allocate human resources?

I have to manage shifts of a variable number of people inside several rooms for a week. Every shift must be at least 1h long and the number of hours per person for the week should be nearly the same ...