# Questions tagged [optimization]

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

430 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
602 views

### Optimal meeting point in directed graph

Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$. I need ...
1k views

### Alternative to Bloom filter for extreme parameters

A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below). I am interested in a ...
749 views

888 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 ...
614 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 ...
184 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 ...
192 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? ...
126 views

39 views

### Does it make sense to examine the dual of a feasbility problem?

Consider a standard feasibility problem. The goal is to examine the state of feasible solutions for $Ax=b$ to find an $x$ that satisfies some property. Does the dual of this problem tell us anything ...
620 views

### Shortest path in a known room for a Roomba

I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search ...
44 views

### Repeated linear programming with similar (not identical) problems

I have multiple linear programming problems of the form: $$Minimize\{c^{T}\cdot x\} s.t. Ax = b, x \ge 0$$ Where $c$ and $A$ are fixed for all the problems. Is there any way to utilize that for a ...