# Questions tagged [optimization]

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

1,252 questions
Filter by
Sorted by
Tagged with
334 views

### Are most metaheuristic algorithms different metaphors for the same method?

Most times I encounter this random metaphors for metaheuristic optimization they seem like a modified genetic algorithm to me. What do you think? Is there a way to remove the analogies/metaphors to ...
127 views

### Bidirectional Search on possible negative weight edges digraphs

There are plenty material about bidirectional search with non-negative edge weights. One example is this paper. I am looking for any improvements using a bidirectional approach for acyclic digraphs ...
2k views

### Optimal strategy for an abstract game

I've been given the following problem in an interview (that I've already failed to solve, not trying to cheat my way past): The game starts with a positive integer number $A_0$. (E.g. $A_0 = 1234$.) ...
69 views

### Select largest subset, subject to a separate weighting constraint

Given an unsorted set of tuples $(c, w)$ and a threshold value $W$, I want to select $k$ tuples such that: $$maximize\sum_{i=1}^k c_i \\ \sum_{i=1}^k w_i \ge W$$ It seems pretty simple at first. ...
24 views

124 views

### Sequence Alignment with Skips

In my thesis I am working on a problem connected with sequence alignment, in particular, I deal with the Dynamic Time Warping (DTW) algorithm (see this for more), which is used to evaluate the ...
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 ...
124 views

### How to schedule n jobs that come at different times on 1 machine (each taking a different time to complete the task)?

Let's say I have to do n jobs, and each job can be done at or after a time T(i) (1<=i<=n). And we have 1 machine and the machine takes a time M to do any job whatsoever. The machine once started ...
169 views

### Design Hashing function from known distribution of bits to be set

How to design Hashing function when the distribution for the bits that will be set are known before hand? Given that the number of bits to be set is constant. The intention is to minimize the hash ...
602 views

### Worst case using the first fit $2$-approximation for the bin packing problem

I am with the phone so I would be more verbose when I will have a pc on hand, if you desire. The first fit algorithm for approximating the bin packing problem (NP-hard) is a $2$-approximation for the ...
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 ...
147 views

### Algorithm to allocate resources to minimize the maximum of any party

I was given the following algorithms problem: Suppose you have $n$ cities. Each city $c_i$ has population $p_i$. You want to construct $m \geq n$ schools, where each school can only serve ...
54 views

### Minimum # toggle (3 consecutive elements) operations to convert ring A into ring B (rings made of Xs and Os: X->O and O->X)

There is a ring A and ring B made of Xs and Os. My aim is to convert A to B by using only the minimum number of # operations. When I do ...
64 views

### Finding the smallest tree of given weight

Take a node-weighted, undirected graph $G$, and a node $r$ in $G$. Is there an efficient algorithm to find a tree in $G$ rooted at $r$ which has total weight at least $w$ and contains a minimal number ...
213 views

### Minimizing transportation cost through a network, multiple source/sinks

I have the following problem: Inputs: A finite collection $V$ of vertices A metric cost function $c:V^2\to\Bbb R$ (interpreted as the edge cost of a complete graph on $V$) An amount of ...
157 views

### How to get the quick answer to the “Is there AT LEAST ONE subset that contains all given elements?” question if the set of subsets is very large?

I have a very large amount of objects that look like this: ...
Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We want to divide ...