Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [optimization]

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

453 questions
Filter by
Sorted by
Tagged with
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 ...
• 516
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 ...
• 391
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 ...
• 11.4k
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 ...
• 6,053
1k views

• 21.7k
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. ...
• 1,165
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 ...
• 1,318
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 ...
• 664
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 ...
• 11.6k
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 ...
• 221
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 ...
• 6,765
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?...
• 259
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. ...
• 531
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 ...
• 947
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, ...
• 769
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 ...
• 242
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 ...
• 563
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 ...
• 295
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 ...
• 1,311
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. ...
• 509
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 ...
• 23.1k
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 ...
• 101
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 ...
• 5,335