# Questions tagged [optimization]

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

1,353 questions
Filter by
Sorted by
Tagged with
36 views

### Text search by first order formula

I am searching for substrings that satisfy a given first order formula in a moderately sized text. The formula is made out of usual $\wedge, \neg, \exists$ and predicates ...
358 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 ...
1k views

### Ant colony optimization for continuous functions

I am trying to do optimization of a voice activity detection function, which is a function with continuous parameters. This is easily accomplished with genetic algorithms, simulated annealing, and ...
855 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 (...
153 views

529 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 ...
213 views

### Is the length of the shortest quine in a programming language computable?

The length of the shortest program in a given (fixed) programming language that produces a given output is that output's Kolmogorov complexity, which is not a computable function on the set of ...
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....
2k views

613 views

### Suboptimal Solution for a combinatorial problem

I have a cost function $f(X)=\|\hat{X}-X\|_2$ to minimize which depends on a $s\times s$ matrix $X$ where $\hat{X}$ is given and $\|X\|_2=\big(\sum_{i,j}x_{ij}^2\big)^{1/2}$. This matrix $X$ is ...
4k views

### What is the best way to index lookups on a 2D array of integers that is boundless in x and y?

Lets say you have a data model that consists of a 2D grid of integer points. This grid is sparsely populated and boundless in x and y (up to the max of a 32-bit integer). What is the best way to ...
631 views

### Boat riddle as a combinatorial optimization problem?

I remember a riddle about a bunch of people on a river bank, and a boat with limited capacity (lets say the boat can transport 2 people at a time). There are various relations between the people like: ...
282 views

### Bin packing problem or not?

Suppose I have $N$ bins and $M$ items as depicted in the figure below (3 bins and 3 items): Suppose that every bin has unit capacity and the weights of the items depend on the bins used. I want to ...
Let $X_1,\dots,X_n$ be $n$ boolean variables. I have an unknown predicate $P(X_1,\dots,X_n)$ on these boolean variables. Of course, I can view the predicate as a function \$f_P : \{0,1\}^n \to \{0,1\}...