# Questions tagged [optimization]

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

456 questions
Filter by
Sorted by
Tagged with
28 views

### Two-stage Robust Shortest Path Problem - worst- case second-stage of an optimal solution

in the paper Improved Approximations for Two-stage Min-Cut and Shortest Path Problems under Uncertainty chapter 4, they are using an algorithm to approximate the two-stage robust shortest path problem....
109 views

### Min-cost perfect matching, but must pick exactly k special edges. Is it NP-hard?

I'd like to know if the following generalization of min-cost perfect matching is NP-hard. As usual, we are given a graph $G = (V,E)$ with costs on edges $c: E \to \mathbb{R}_{\geq 0}$. In addition, ...
• 649
120 views

### Are there NPO (NP Optimization) problems that would require more than polynomial time even on a non-deterministic machine?

Consider an $\mathit{NPO}$ problem $O = (X,L,f,\mathit{opt})$ according to the definition of $\mathit{NPO}$ found in this answer. What I don't fully understand is what happens if we use a NDTM (non-...
58 views

### Is there optimal or approximate solution to Single-machine scheduling problem with constraints?

I'm interested in particular setup of Single-machine scheduling. I'll use the Optimal job scheduling notation to specify the situation. I'm also aware of Interval scheduling. What I want to achieve is ...
1k views

### What is the fastest static comparison sort? What is the proper term for "static"?

In a standard comparison sort, you perform a comparison and your next action is based off of the result of that comparison. What if this was not allowed, and you had to request all the results at the ...
• 299
1 vote
96 views

### Non-convex optimization with correlated minima

I am thinking of non-convex optimization problems where the minima are somehow correlated. Maybe there are symmetry relationships among minima or maybe there is regularity in spacing among minima in ...
• 661
76 views

### What work on min max connectivity problems has there been?

For instance has min max spanning/steiner/prize-collecting tree been studied. i.e. each edge $e$ has costs $c_{v,e}$ of each resource $i$. And we wish to find a spanning tree minimizing the maximum ...
• 228
70 views

### Has multiobjective prize collecting steiner tree or TSP been studied?

Suppose we have a graph $G$ a root $r$ and each node $v$ has some amount of $c_{v,i}$ of each resource $i$. I connect a set of nodes to the root that maximizes the minimum amount of any resource using ...
• 228
55 views

### cutting plane method for convex optimization

The cutting plane approach in convex optimization is a general recipe for minimizing a convex function. The argument relies on the fact that using the gradient vector, we can cut the feasible set into ...
• 101
60 views

232 views

### Can the ellipsoid method be used with a randomized separation oracle?

Suppose we are trying to solve the following optimization problem: $$\text{maximize } ~~ c\cdot y \\ \text{subject to } ~~ y\in S$$ where the region $S$ is described by an exponential number of ...
• 101
86 views

### Submodular welfare maximization: what is the best known approximation ratio of a deterministic algorithm?

In the submodular welfare maximization problem, there is a set $M$ of items that should be partitioned among $n$ agents. Each agent $i$ has a value function $v_i: 2^M\to \mathbb{R}_+$. All value ...
• 2,294
98 views

### How to prove that a given class of convex programs cannot be solved by linear programming?

Given the following program, where $f, g$ are convex functions: $$\text{minimize}~~ f(x) \\ \text{subject to}~~ g(x)\leq 0$$ the problem can be solved by convex programming algorithms, but it would ...
• 2,294
44 views

### Computational complexity of CVaR calculation

I am currently looking for literature discussing the computational complexity of CVaR calculation. At this point the only work I have found is the following. Mavronicolas, Marios, and Burkhard Monien. ...
• 661
199 views

### Solving linear programs with special structure

We have an application and at some point we need to solve a linear programming problem that looks like this:  \min\ w_{1,2} + w_{3,4} + w_{5,6}\\ x_i - x_j \leq c_{ij},\ \forall\ (i,j) \in C\\ x_1 - ...
• 73
226 views

### What is this graph problem, and how hard is it?

My problem is quite simple to state, so it surely must have a name: Given a graph $G=(V,E)$ with edge weights $w(e) \in \mathbb{Z}$, find a $V' \subseteq V$ that maximizes $\sum_{e \in E' } w(e)$, ...
• 31
1 vote
83 views

### A bound that follows from submodularity

I am studying Lemma 1 of this paper: The Adaptive Complexity of Maximizing a Submodular Function. The proof appears on page 11. I got stuck on this inequality: where $f$ is a monotone submodular set ...
• 113
1 vote
66 views

• 1,582
1 vote
85 views

### Packing k vertex trees

Consider a graph $G=(V,E)$ with $n$ vertices. What do we know about packing of $k$ vertex trees, Both integral and fractional packing are interesting. $k=2$, it is just the number of edges, hence ...
• 4,509
27 views

### Quantifying the cost of procedures

Is there any research on quantifying the cost of a procedure, with regard to compiler optimization? I.e. assigning some kind of cost in terms of CPU time or memory to a procedure, either so the ...
• 111
79 views

### Solving MDPs with polytope action spaces

A (finite) Markov Decision Process (MDP) consists of a finite set of states $S$, a finite set of actions $A_s$ which we will allow to depend on the state $s\in S$, an initial state $s_0\in S$ (the ...
• 2,181
1 vote
58 views

### Find the minimum cost spider joining a root to some leaves

A spider is a tree with at most one vertex of degree greater than 2. This vertex is called the head of the spider. I am interested in the following problem: We are given an undirected graph $G = (V,E)$...
• 649
1 vote
64 views

### The tree augmentation problem, but with hyperlinks

In the (Weighted) Tree Augmentation Problem, we are given a tree $T = (V,E)$ and a set of additional edges $L$ called links with non-negative costs. Each link $\ell = (u,v)$ covers the tree edges ...
• 649
254 views

### Tensor network contraction "bubbling": why are some approaches more computationally efficient than others (question from a beginner)

I am learning the very basics of tensor network theory and I am trying to understand why some ways to contract tensors are better than others in terms of computational complexity. Knowing in which ...
1 vote
109 views

### Growth rate of Knapsack Solutions

Let's say I have a Knapsack with capacity $\tau$, and I have an infinite sequence of items with weights $(a_n)_{n=1}^{\infty}$. A feasible Knapsack solution is a subset $S \subset \mathbb{N}$ such ...
• 627
215 views

### Maximize a special monotone submodular function - is it easier?

I am looking for a way to optimize the function $f$, defined below. First, fix some positive integer $k$ and let $c_1$ and $c_2$ be non-negative vectors in $\mathbb{R}^n$. Let $g$ be an increasing ...
• 649
90 views

### Parameterized Complexity of Vertex Multicut

Let $G$ be an undirected graph, $\{(s_1,t_1),\dots,(s_k,t_k)\}$ a collection of pairs of vertices, and $p$ an integer. The Vertex Multicut problem asks if there is a set $S$ of at most $p$ vertices ...
• 103