Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
23 votes
2 answers
3k 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 ...
  • 10.9k
31 votes
2 answers
963 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 ...
  • 516
6 votes
1 answer
303 views

Is this edge orientation optimization problem NP-hard?

Is the following optimization problem NP-hard? Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\...
  • 553
9 votes
2 answers
1k 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$...
8 votes
3 answers
559 views

Is that edge orientation optimization problem NP-hard?

Is the following optimization problem NP-hard? Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{...
  • 553
4 votes
2 answers
334 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\...
  • 53
4 votes
1 answer
299 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}$. ...
  • 10.9k
4 votes
1 answer
381 views

Approximation algorithms for min vector subset-sum over GF(2)

In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum. Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing to ...
  • 1,318
23 votes
3 answers
1k 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 ...
21 votes
1 answer
3k views

Solving semidefinite programs in polynomial time

We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (...
  • 1,571
14 votes
1 answer
728 views

Second Smallest $s$-$t$-Cut in a Network

Is anything known about the second smallest $s$-$t$-cut in a flow network? Or, more general, about this problem: Input: A network $N$ and a number $k$, all in binary. Output: A $k$th smallest $s$-...
13 votes
1 answer
939 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{...
10 votes
1 answer
566 views

Is the following graph optimization problem approximable within a constant factor?

Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of ...
  • 553
7 votes
1 answer
815 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} ...
  • 263
7 votes
3 answers
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 ...
  • 348
6 votes
1 answer
306 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 $\...
  • 2,281
5 votes
2 answers
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: ...
5 votes
0 answers
467 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
1 answer
513 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 ...
  • 175
4 votes
1 answer
259 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 ...
  • 41
4 votes
1 answer
464 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
1 answer
445 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 ...
  • 231
4 votes
2 answers
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.
3 votes
2 answers
170 views

Minimum relevant variables in linear system - additive approximation

In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.: $$ A x = b $$ and the goal is to find a solution $x$ with as few nonzero variables as ...
3 votes
0 answers
95 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 ...
  • 1,167
3 votes
2 answers
424 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 ...
  • 779
3 votes
1 answer
102 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
3 answers
484 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 ...
  • 31
2 votes
1 answer
457 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 ...
  • 749
2 votes
1 answer
253 views

Is this node permutation optimization NP-Hard?

Let $G=(V,E)$ be an undirected graph and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{succ}_{\pi}(v)$ the set of neighbors of $v$ that occur after $v$ in ...
  • 553
2 votes
2 answers
502 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_{...
  • 467
1 vote
0 answers
154 views

Is the matching polytope integral?

In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf they prove the integrality of the matching polytope using the integrality of the perfect matching polytope. The ...
0 votes
1 answer
687 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. ...