Questions tagged [optimization]

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

1,179 questions
163k views

What is a the fastest sorting algorithm for an array of integers?

I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are: Which is the fastest ...
7k views

3k views

Why do low fitness individuals have a chance to survive to the next generation?

I am currently reading and watching about genetic algorithm and I find it very interesting (I haven't had the chance to study it while I was at the university). I understand that mutations are based ...
1k views

How fundamental are matroids and greedoids in algorithm design?

Initially, matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy ...
2k views

Collectively pay the bill problem

There are $n$ people at a table. The $i$th person has to pay $p_i$ dollars. Some people don't have the right bills to pay exactly $p_i$, so they come up with the following algorithm. First, ...
2k views

Why are NP-complete problems so different in terms of their approximation?

I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory. One thing that I've noticed is that while many problems are NP-complete, when ...
1k views

394 views

Is this special case of a scheduling problem solvable in linear time?

Alice, a student, has a lot of homework over the next weeks. Each item of homework takes her exactly one day. Each item also has a deadline, and a negative impact on her grades (assume a real number,...
1k views

Algorithm to match numbers with minimum number of moves

This is a sort of edit-distance question, and is very easy. I am just quite brain dead on this subject and can't figure it out so far. Given a series of numbers, e.g. ...
3k views

What is a bicriteria approximation algorithm?

What is a bicriteria approximation algorithm? This keeps coming up in the case of data stream clustering. Is this related to multi-objective optimization? This is where I came across it: cis.upenn....
7k views

Data Science vs Operations Research

The general question, as the title suggests, is: What is the difference between DS and OR/optimization. On a conceptual level I understand that DS tries to extract knowledge from the available data ...
1k views

Minimize the maximum component of a sum of vectors

I'd like to learn something about this optimization problem: For given non-negative whole numbers $a_{i,j,k}$, find a function $f$ minimizing the expression $$\max_k \sum_i a_{i,f(i),k}$$ An example ...
1k views

Finding exact corner solutions to linear programming using interior point methods

The simplex algorithm walks greedily on the corners of a polytope to find the optimal solution to the linear programming problem. As a result, the answer is always a corner of the polytope. Interior ...
543 views

A continuous optimization problem that reduces to TSP

Suppose I am given a finite set of points $p_1,p_2,..p_n$ in the plane, and asked to draw a twice-differentiable curve $C(P)$ through the $p_i$'s, such that its perimeter is as small as possible. ...
10k views

476 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 ...
854 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 ...
282 views

How fast can we compute the size of maximum matching in an unweighted bipartite graph?

Is there a way to compute the size of a maximum matching in an unweighted bipartite graph more efficiently (e.g. faster) than computing a maximum matching? It is a long shot but it is often an ...
665 views

322 views

How do I classify my emulator input optimization problem, and with which algorithm should I approach it?

Due to the nature of the question, I have to include lots of background information (because my question is: how do I narrow this down?) That said, it can be summarized (to the best of my knowledge) ...
7k views

What algorithm would compute the maximum choices from two sets?

Given two vectors of integers of possibly unequal lengths, how can I determine the maximum result possible from accumulating choosing the maximum between corresponding pairs of numbers between the two ...
535 views

192 views

Is this combinatorial optimisation problem similar to any known problem?

The problem is as follows: We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a ...
248 views

Ordering elements so that some elements don't come between others

Given an integer $n$ and set of triplets of distinct integers $$S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\},$$ find an algorithm which either finds a permutation $\pi$...
What is the complexity of MIN-2-XOR-SAT and MAX_2-XOR-SAT? Are they in P? Are they NP-hard? To formalize this more precisely, let $$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,$$ where $\... 1answer 428 views Easy way to prove that this algorithm eventually terminates Introduction and notations: Here is a new and simple version of my algorithm which seems to terminates (according to my experiments), and now I would like to prove that. Let the notation$x_i \in \...
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 ...