Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
31 votes
2 answers
1k 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 ...
Bart's user avatar
  • 516
28 votes
5 answers
6k views

Is it a rule that discrete problems are NP-hard and continuous problems are not?

In my computer science education, I increasingly notice that most discrete problems are NP-complete (at least), whereas optimizing continuous problems is almost always easily achievable, usually ...
alekdimi's user avatar
  • 391
26 votes
3 answers
1k views

Optimization problems with minimax 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 ...
Andras Farago's user avatar
26 votes
1 answer
585 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 ...
Gil Kalai's user avatar
  • 6,053
25 votes
3 answers
1k views

Rounding to minimise the sum of errors in pairwise distances

What is known about the complexity of the following problem: Given: rational numbers $x_1 < x_2 < \dotso < x_n$. Output: integers $y_1 \le y_2 \le \dotso \le y_n$. Objective: minimise $$\...
Jukka Suomela's user avatar
23 votes
2 answers
4k 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 ...
vzn's user avatar
  • 11k
23 votes
3 answers
1k views

Clique problem on fixed graphs

As we know, the $k$-clique function $CLIQUE(n,k)$ takes a (spanning) subgraph $G\subseteq K_n$ of a complete $n$-vertex graph $K_n$, and outputs $1$ iff $G$ contains a $k$-clique. Variables in this ...
Stasys's user avatar
  • 6,765
23 votes
5 answers
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 ...
Simd's user avatar
  • 3,902
22 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 (...
Arindam Pal's user avatar
  • 1,591
21 votes
2 answers
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 ...
Peter Shor 's user avatar
19 votes
1 answer
470 views

Finding good induced subgraph

You are given a graph $G = (V,E)$ with $n$ vertices. It might be bipartite if you want. There are $m$ sets of edges $E_1,\ldots, E_m \subseteq E$ (say disjoint). I am interested in the problem of ...
Sariel Har-Peled's user avatar
18 votes
2 answers
940 views

Solving a Number-Hopper Maze

My 8-yr old has gotten bored creating conventional mazes, and has taken to creating variants that look like this: The idea is to start from x and reach o via the normal rules. Additionally, you can "...
Fixee's user avatar
  • 1,003
17 votes
2 answers
416 views

Minimal cumulative set sum

Consider this problem: Given a list of finite sets, find an ordering $s_1, s_2, s_3, \ldots$ that minimizes $|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots$. Are there known algorithms ...
Antimony's user avatar
  • 917
16 votes
1 answer
1k views

Solving a linear diophantine equation approximately

Consider the following problem: Input: a hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$, given by a vector $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ in ...
Sasho Nikolov's user avatar
15 votes
4 answers
1k views

What's new in compiler optimization techniques over last few years?

I'm interested in optimization of data flow and control flow graphs and in particular more computationally complex. But it will also be interesting to know about the latest inventions in the field of ...
Evgeny Gavrin's user avatar
15 votes
3 answers
557 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 - ...
Vladimir Panteleev's user avatar
14 votes
4 answers
2k views

Theoretical study of coordinate descent methods

I'm preparing some course material on heuristics for optimization, and have been looking at coordinate descent methods. The setting is here a multivariate function $f$ that you wish to optimize. $f$ ...
Suresh Venkat's user avatar
14 votes
2 answers
984 views

Complexity of optimization over unitary group

What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$? A typical task, arising often in quantum information theory, would be maximizing a ...
Marcin Kotowski's user avatar
14 votes
1 answer
893 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$-...
Oliver Witt's user avatar
14 votes
2 answers
1k views

0-1 Linear Programming: computing the Optimal Formulation

Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in ...
Giorgio Camerani's user avatar
14 votes
1 answer
1k views

Does zero integrality gap imply zero duality gap for certain problems?

We know that if the gap between the values of an integer program and its dual (the "duality gap") is zero, then the linear programming relaxations of the integer program and the dual of the relaxation,...
Ankur's user avatar
  • 779
14 votes
1 answer
434 views

What is the state of the art in cache algorithm theory?

I recently became interested in the general problem of optimizing memory usage in a situation where there is more than one kind of memory available, and there is a trade-off between the capacity of a ...
Superbest's user avatar
  • 241
13 votes
3 answers
1k views

Successful application of branch-and-bound methods for NP-hard problems

Branch and bound is an effective heuristic for search problems, and Wikipedia lists a number of hard problems where branch-and-bound has been used. However, I haven't been able to find references to ...
Suresh Venkat's user avatar
13 votes
2 answers
387 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 "...
Anthony Labarre's user avatar
13 votes
1 answer
996 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{...
Jukka Suomela's user avatar
13 votes
2 answers
427 views

Linear time algorithm for finding shifted max

Assume that we are given an array $A[1..n]$ containing nonnegative integers (not necessarily distinct). Let $B$ be $A$ sorted in the nonincreasing order. We want to compute $$m = \max_{i\in [n]} B[i]...
Kaveh's user avatar
  • 21.7k
13 votes
1 answer
886 views

Numerical stability of Simplex method

The simplex algorithm is often treated either within real arithmetic, or in the discrete world with exact computations. However, it seems to be implemented most often with floating-point arithmetic. ...
shuhalo's user avatar
  • 1,165
13 votes
2 answers
639 views

Numerical precision in sum-of-squares method?

I have been reading a bit about the sum-of-squares method (SOS) from the survey of Barak & Steurer and the lecture notes of Barak. In both cases they sweep issues of numerical accuracy under the ...
Jeremy Kun's user avatar
  • 1,318
12 votes
5 answers
573 views

Submodular functions: reference request

I would be very much interested in references to the theory of submodular functions (from basics to advanced). In particular, I am studying approximations to hard optimization problems and I want to ...
Nikhil's user avatar
  • 664
12 votes
2 answers
906 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 ...
Jukka Suomela's user avatar
12 votes
2 answers
1k views

What is this variant of set cover problem known as?

Input is a universe $U$ and a family of subsets of $U$, say, ${\cal F} \subseteq 2^U$. We assume that the subsets in ${\cal F}$ can cover $U$, i.e., $\bigcup_{E\in {\cal F}}E=U$. An incremental ...
Alex's user avatar
  • 221
12 votes
0 answers
367 views

How good is greedy in average?

Given a family ${\cal F}\subset 2^E$ of (feasible solutions), the maximization problem on ${\cal F}$ is, for every weighting $x:E\to \{0,1,\ldots\}$ of ground elements, to compute the maximum weight ...
Stasys's user avatar
  • 6,765
12 votes
0 answers
282 views

the largest element of a matrix product

Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to require?...
MWB's user avatar
  • 259
12 votes
0 answers
298 views

Expected length of a self-avoiding random walk

We're given an arbitrary graph $G=(V,E)$. A self-avoiding random walk is a random walk such that in each step, a random neighbour which was not previously visited is chosen, if such one exists. ...
JoelO's user avatar
  • 531
11 votes
2 answers
285 views

Easy to optimize but hard to evaluate

Are there any known natural examples of optimization problems for which it is much easier to produce an optimal solution than to evaluate the quality of a given candidate solution? For the sake of ...
david's user avatar
  • 947
11 votes
3 answers
446 views

min hitting set of every base of a matroid

We are given a matroid. Our goal is to find a set of elements of minimum size that has non-empty intersection with every base of the matroid. Is the problem studied before? Is it in P? For example, ...
jian's user avatar
  • 769
11 votes
4 answers
928 views

Reordering data (set of strings) to optimize for compression?

Are there any algorithms for reordering data to optimize for compression? I understand this is specific to the data and the compression algorithm, but is there a word for this topic? Where can I ...
Jayen's user avatar
  • 242
10 votes
1 answer
617 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 ...
maxdan94's user avatar
  • 563
10 votes
3 answers
953 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 ...
mhadley's user avatar
  • 295
10 votes
1 answer
226 views

Program Minimization

Circuit Minimization is the problem to minimize the size of a given circuit. Is there anything similar for general programs? In particular my question is - Do there exist algorithms to minimize the ...
Opt's user avatar
  • 1,311
10 votes
2 answers
2k views

Sorting points such that the minimal Euclidean distance between consecutive points would be maximized

Given a set of points in a 3D Cartesian space, I am looking for an algorithm that will sort these points, such that the minimal Euclidean distance between two consecutive points would be maximized. ...
Lior Kogan's user avatar
10 votes
0 answers
243 views

Complexity of cycle cancellation with integral capacities and irrational costs

Cycle cancellation is a standard textbook algorithm for computing minimum-cost circulations: As long as the residual graph of the current circulation contains a negative cycle, push as much flow along ...
Jeffε's user avatar
  • 23.1k
10 votes
2 answers
733 views

Set optimization problem - is it np-complete?

Set $S=\{e_1,\cdots,e_n\}$ is given. For each element $e_i$, we have weight $w_i>0$ and cost $c_i>0$. The goal is findIng the subset $M$ of size $k$ that maximize the following objective ...
Nasooh's user avatar
  • 101
9 votes
3 answers
3k views

How/Why are linear systems so crucial to computer science?

I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network ...
PhD's user avatar
  • 5,335
9 votes
1 answer
613 views

Minimum spanning tree over all vertex matchings

I ran into this matching problem for which I am unable to write down a polynomial time algorithm. Let $P, Q$ be complete weighted graphs with vertex sets $P_V$ and $Q_V$, respectively, where $|P_V| =...
M.B.'s user avatar
  • 313
9 votes
2 answers
351 views

A variation on discrepancy involving random graphs

Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $−1$. Call this a configuration $\sigma \in \{+1,−1\}^n$. The number of $+1$s that we have to assign is ...
passerby51's user avatar
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$...
Alejandro Piad's user avatar
9 votes
1 answer
6k views

Quantum annealing vs adiabatic quantum computation

I had this impression that quantum annealing is an optimization technique which may or may not produce exact solutions. On the other hand adiabatic quantum computation always gives exact solutions ...
Omar Shehab's user avatar
9 votes
1 answer
375 views

Is the complexity of this covering problem known?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
Thomas Kalinowski's user avatar
9 votes
1 answer
345 views

Heuristics for Optimization

Since it's Friday, it's time for a CW question. I'm looking for heuristics that have wide use in optimization problems. To limit the scope to more 'theory-friendly' heuristics, here are the rules (...

1
2 3 4 5
10