The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [optimization]

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

351 questions
Filter by
Sorted by
Tagged with
1answer
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 ...
0answers
745 views

### Algorithm to maximize profit: ways to solve/approach? (Advanced NP-Complete)

This one's hard, so all help really appreciated! I know it is NP-Complete and thus cannot be solved in polynomial time, but looking for help in analysis, i.e. what type of NP-Complete problem it ...
3answers
655 views

### Hardness of MAX-CUT on sparse graphs

Let a weighted graph $G(V,E)$, where the weights are real (positve and negative). Assume that $G$ has $\mathcal{O}(n\log n)$ edges. How fast can we compute MAX-CUT on this graph? Can we compute (...
0answers
151 views

### covering an NxN grid using overlapping vs. non-overlapping windows residing k points in each

Let the problem, $P_{overlapping}$, be the following. We have an $N_1 \times N_2$ grid. Each cell of the grid can have the value either 0 or 1. Assume that we have $a \times b$ overlapping windows as ...
2answers
525 views

### Capacitated multiple vehicle routing problem with handovers

I'm looking for literature about a variant of the capacitated vehicle/fleet routing problem (a.k.a. VRP, CVRP, etc.) that takes into account the possibility of handovers between multiple vehicles, i.e....
2answers
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. ...
1answer
313 views

### On which classes of graphs is resource constrained shortest path (RCSP) NP-hard?

I'm looking to link a problem I'm working on to a known NP-hard problem. I think I can model my problem as a resource constrained shortest path problem. However, the structure of my graph is not ...
1answer
635 views

### Maximizing strictly increasing convex function

Let the objective be to maximize the sum of $f_i(x_i)$ where all $f_i$ are strictly increasing convex functions. Maximizing a convex function is hard as a local maximum might not be a global one. ...
0answers
715 views

### Is this minimization problem NP-Complete?

We are given an $n \times (n + k)$ matrix $A$, with entries in GF(2), of the form $A =[I_n\ B]$, where $I_n$ is the $n \times n$ identity matrix, and $B$ has no "zero" rows or columns. The problem is ...
1answer
369 views

### Place n points in a box as far away from each other as possible

Can you suggest an optimal or heuristic algorithm for placing points on a 2D plane (within a constrained space) such that minimum distance between any two points is maximized. In other words, I'm ...
2answers
240 views

### Inferring an LP cost vector from its solution

Say I have the following linear programming formulation in standard form: \begin{equation*} \begin{array}{rl} \mathbf{x}^* = \underset{\mathbf{x}}{\text{arg}\;\text{min}} & \mathbf{c}^...
1answer
158 views

### Local Smoothness vs optimisation in combinatorial problems

Local smoothness is often mentioned in literature analysing different heuristics and meta-heuristics for combinatorial optimisation. What is meant precisely by local smoothness is often left out, but ...
3answers
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 ...
1answer
300 views

### why are the constraints in the following paper tight?

My question is about the following paper: http://webdocs.cs.ualberta.ca/~maz/publications/ratliff_nathan_2007_3.pdf In section 2 they show Equation 3 (which is just an optimization problem), which ...
4answers
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$ ...
4answers
467 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 ...
1answer
203 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 ...
4answers
1k views

### Genetic Algorithm to Draw a Graph? Position assignment problem

I have an assignment problem at hand and am wondering how suitable it would be to apply local search techniques to reach a desirable solution (the search space is quite large). I have a directed ...
1answer
170 views

### Combinatorial algorithm for optimization over semimetric polytope

This question is motivated by the Leighton-Rao relaxation for SPARSEST-CUT. Suppose one wants to find a non-trivial semimetric over an $n$-point space that minimizes a certain linear functional. More ...
0answers
121 views

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 ...
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 ...
3answers
784 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 ...
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 ...
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.
3answers
506 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 - ...
2answers
865 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 ...
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 ...
1answer
449 views

### Approximately sampling from convex polyhedrons with quantum computers

Quantum computers are very good for sampling distributions that we dont know how to sample using classical computers. For example if f is a Boolean function (from $\{-1,1\}^n$ to ${-1,1}$) that can be ...
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 ...
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 ...
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. ...