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
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 ...
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 ...
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 (...
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 ...
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....
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. ...
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 ...
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. ...
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 ...
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 ...
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}^...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
121 views

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 ...
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 ...
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 ...
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 ...
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.
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 - ...
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 ...
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 ...
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 ...
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 ...