Questions tagged [optimization]

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

17
votes
1answer
2k views

computing the minimal NFA for a DFA

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known ...
30
votes
2answers
862 views

What classes of mathematical programs can be solved exactly or approximately, in polynomial time?

I am rather confused by the continuous optimization literature and TCS literature about which types of (continuous) mathematical programs (MPs) can be solved efficiently, and which cannot. The ...
9
votes
2answers
770 views

Generating interesting combinatorial optimization problems

I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$...
4
votes
2answers
209 views

Iteratively minimizing the function

Consider the problem \begin{equation} \min_{x\in X, y \in Y} f(x,y) \end{equation} Can I solve the problem by iteratively solving the following two sub problems? \begin{equation} x_{k+1} = \arg\...
4
votes
1answer
196 views

minimal finite automata given in-words and out-words

this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight. given: two finite sets of words $S_{in}$ and $S_{out}$. ...
23
votes
3answers
891 views

Optimization problems with good characterization, but no polynomial-time algorithm

Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the ...
4
votes
2answers
2k views

Finding the two shortest paths while minimizing the number of nearby/common edges

The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary. Consider the following variant: ...
3
votes
0answers
87 views

Showing hardness of maximizing stochastic objective function over graph

Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$. The challenge is to ...
0
votes
1answer
644 views

To what extent is it possible to use genetic algorithms to make wind mill turbine blades more efficient?

I recently watched this video on youtube. It featured someone explaining how he used genetic algorithms to improve the efficiency of wind mill turbines by finding the optimal shape for the blades. ...
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 ...
7
votes
1answer
569 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} ...
4
votes
1answer
385 views

Proof that the graph optimization problem is NP-hard

I'm trying to prove that the following optimization problem is NP-hard: Given a graph $G=(V,E)$, non-negative vertex weight functions $w(v)$ and $s(v)$, and a non-negative edge weight function $t(u,v)...
4
votes
1answer
296 views

Modifying Edmonds' Blossom Algorithm

Given a connected road network on an Island without one-way streets, where should I para-shoot in and what route should I take to deliver mail to all houses on the island (being picked up again by ...
4
votes
1answer
418 views

Minimum Union-Sum Cost Path

I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path ...
4
votes
2answers
2k 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.
2
votes
2answers
474 views

Is the following optimization problem NP-hard?

Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$, is given. E.g. $S=\{(1,3), (2,3), (1,4), (2,4), (3,1), (3,4)\}$ . For each element $(i,j)$, we have weight $w_{...
13
votes
1answer
792 views

Exact algorithms for non-convex quadratic programming

This question is about quadratic programming problems with box constraints (box-QP), i.e., optimisation problems of the form minimise $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{...
6
votes
1answer
292 views

Approximation schemes for P-complete problems?

What work has been done on approximation schemes for $\mathsf{P}$-complete optimization problems? Would the desired approximation algorithms here be "fully log-space approximation schemes" or "fully $\...
5
votes
0answers
389 views

lower bound for difference between max cut and min cut

Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e. $$M^+=\max\limits_{(U_1,U_2)}\left\{\sum_{e=\{u,v\}\...
4
votes
1answer
200 views

Laying paths on a network using minimum number of links/edges

Consider an undirected graph G(V,E), where each edge $e\in E$ has capacity $c(e)$. Also given is a traffic matrix $T_{ij}$ representing the amount of traffic flowing from vertex $i$ to $j$. The goal ...
3
votes
1answer
92 views

Questions about Farhi's pre-Adiabatic paper

I have been going through Eddie Farhi's 6-pages long pre-Adiabatic paper, An Analog Analogue of a Digital Quantum Computation. I guess I understand most of the math and physics but I am struggling ...
3
votes
3answers
376 views

Facility location problem with a cost function

I'm struggling with a facility location problem. In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from ...
2
votes
2answers
306 views

Undecidability of program optimization

A program is an encoded Turing Machine. And a size optimizer of a program is a TM $M_1$ such that: On any input $M$, $M_1$ outputs $M_{min}$ such that $M_{min}$ is the shortest TM which is ...
2
votes
1answer
367 views

Follow the Perturbed Leader for nonlinear cost functions

The famous FTPL algorithm [1] is analyzing linear cost function. Is there any generalized proof for nonlinear functions known? Note that in the last paragraph of [1] it says "It would be great to ...