Questions tagged [optimization]

general questions about selecting a best element from some set of available alternatives.

Filter by
Sorted by
Tagged with
13
votes
2answers
378 views

Survey of transformations related to the use of SAT solvers

I am starting to investigate the possibility of relying on a SAT solver to tackle an optimisation problem I'm interested in, and am currently looking for a survey that would feature examples of "...
2
votes
2answers
118 views

Asking optimal questions to differentiate object in set

I have a problem in mind and I am sure this is likely an area of active research, but am at a loss as to the correct terminology and thus unable to find any reference literature. It is best explained ...
4
votes
2answers
2k views

Detecting infeasibility of System of Linear Inequalities

Infeasibility of a system of linear inequalities can be detected by using artificial variables and then using an algorithm like the simplex algorithm (or ellipsoid/interior point methods) to find a ...
2
votes
1answer
822 views

Survey on Optimization algorithms

I am trying to solve an optimization problem. I need some help in getting the results or survey on related issues. The question is a bit general but any help in identifying the correct sources would ...
7
votes
1answer
647 views

Is minimax problem NP-Hard when the inner problem is NP-Hard ?

Consider a minimax problem of the form: $\min_{x\in X} \max_{u\in U} f(x,u)$ The outer problem $\min_{x\in X} f(x,u)$ for any given $u$ is polynomially solvable. If the inner problem $\max_{u\in U} ...
23
votes
5answers
2k views

Packing rectangles into convex polygons but without rotations

I am interested in the problem of packing identical copies of (2 dimensional) rectangles into a convex (2 dimensional) polygon without overlaps. In my problem you are not allowed to rotate the ...
1
vote
1answer
154 views

Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation?

Let's say I had an optimization problem $$ \min_{x \in D} f(x) $$ Where $D \subset \mathbb{R}^n$ and $f:\space D \rightarrow \mathbb{R}$, and the minimum is said to exist. Imagine I had a ...
10
votes
3answers
862 views

Applications of MCTS/UCT

MCTS/UCT is a game tree search method that uses a bandit algorithm to select promising nodes to explore. Games are played to their completion randomly and nodes leading to more wins are explored more ...
21
votes
2answers
3k views

How good is the Huffman code when there are no large probability letters?

The Huffman code for a probability distribution $p$ is the prefix code with the minimum weighted average codeword length $\sum p_i \ell_i$, where $\ell_i$ is the length of the $i$th codword. It is a ...
4
votes
2answers
3k views

Why does the Fibonacci sequence produce a worst-case Huffman encoding?

I noticed this in my Algorithms class, but just now got around to asking.
15
votes
3answers
531 views

Bob's Sale (reordering of pairs with constraints to minimize sum of products)

I've asked this question on Stack Overflow a while ago: Problem: Bob's sale. Someone suggested posting the question here as well. Someone has already asked a question related to this problem here - ...
12
votes
2answers
885 views

Minimum maximal solutions of LPs

Linear programming is, of course, nowadays very well understood. We have a lot of work that characterises the structure of feasible solutions, and the structure of optimal solutions. We have the ...
8
votes
1answer
2k views

What's the difference between online and incremental optimization?

Recently I've read some stuff about incremental optimization problems, but I can't see what's the difference between those and online optimization problems. My impression is that I can define every ...
25
votes
1answer
524 views

Approximately sampling from convex polyhedrons with quantum computers

Quantum computers are very good for sampling distributions that we don't know how to sample using classical computers. For example if $f$ is a Boolean function (from $\{-1,1\}^n$ to $\{-1,1\}$) that ...
7
votes
3answers
2k views

A simple approximation algorithm for the TSP

Consider the following extremely simple approximation algorithm for the TSP. Input: A complete weighted graph $G=(V,E).$ Take any three vertices $a,b,c\in V$ and let $H:=(a,b,c,a).$ While there ...
3
votes
2answers
170 views

Find the right/best track combination for a given distance, using a genetic algorithm or ?.

I have a list of tracks (model railroad tracks) with different length, example: TrackA on 3.0cm, TrackB on 5.0cm, TrackC on 6.5cm, TrackD on 10.5cm Then I want to find out of what kind of track I ...
5
votes
2answers
1k views

Is the following problem NP-Hard?

I'm not expert on complexity theory and combinatorial optimization. I want to know if the following problem (or similar) is known in the scientific literature, and if you think it is NP-complete. ...
5
votes
3answers
417 views

Is there a way to solve an optimization problem where a decision variable shows up in an upper bound (or lower bound) of summation?

minimize/maximize $\displaystyle \sum_{i=0}^{f(n)} G(x,n)$ s.t. $n \ge 1$ and $x$ in some feasible region The decision variables are $x$ (a vector) and $n$ (a scalar). How is this type of ...

1
4 5 6 7
8