Questions tagged [optimization]
general questions about selecting a best element from some set of available alternatives.
456
questions
0
votes
0
answers
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....
4
votes
1
answer
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
0
votes
1
answer
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-...
- 11
0
votes
0
answers
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 ...
- 1
7
votes
3
answers
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
0
answers
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
0
votes
0
answers
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
0
votes
0
answers
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
0
votes
0
answers
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
-1
votes
1
answer
60
views
Computability/Complexity of optimization problems in general
Dear StackExchange community,
I have a question, or better phrased I am confused and would like to be enlightened by you!
So assume we have a (optimization) problem like that:
Instance: Let $f:\...
- 3
1
vote
0
answers
47
views
Convergence rates for the iterates of SGD on Lipschitz convex functions
Let $f:X \rightarrow \mathbb{R}$ be a convex and $L$-Lipschitz continuous function. Suppose $f^* = \min_{x \in X} f(x) \in \mathbb{R}$ and let $X^* = \{x \in X : f(x) = f^*\}$.
For a non-negative ...
- 319
1
vote
0
answers
45
views
Placing a circle in a point cloud
I need to place a circle with fixed radius in a cloud of points. The circle also must lay in a polygon (the points are also in that polygon) This circle has to contain as many points as possible. Are ...
- 11
3
votes
0
answers
83
views
Hardness of Approximation for Three Matroid Intersection
I am searching for the best known hardness of approximation bound for three matroid intersection. The input is three matroids on the same ground set which are accessible using three different ...
- 31
4
votes
1
answer
237
views
Is Optimal Swap Sorting NP-Hard?
Given an array of integers with duplicates, find the minimum number of swaps to sort the array. According to this question, the problem is NP-Complete but the reference given proves NP-Completeness ...
- 135
3
votes
2
answers
173
views
Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes
Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes.
Does this have a constant approximation?
($p,k$ and the graph are all part of the ...
- 228
2
votes
1
answer
112
views
Maximum cardinality disjoint cycle cover in undirected graphs
I call a maximum cardinality disjoint cycle cover of a graph a vertex-disjoint cycle cover containing the maximum possible number of cycles in the graph. What is known about the complexity of this ...
- 828
0
votes
0
answers
65
views
Is there an algorithm that finds a minimum vertex cover with an approximation factor of 3/2 for a planar graph?
Is there an algorithm that finds a minimum vertex cover with an approximation factor of 3/2
for a planar graph?
2
votes
1
answer
131
views
Is beta normalization used for program optimization?
Beta normalization reduces a lambda term to its beta normal form, if it exists. The beta normal form is a computationally equivalent term with no "redundant" computation, in a sense; for ...
- 105
0
votes
0
answers
34
views
Nonlinear GAP similar to Min-GAP but with minimum quantities and without capacity
I have $m$ items and $n$ bins where each item $i$ and bin $j$ has a value $v_{i,j}$. Each bin $j$ has a value $V_j$. I want to pack the items into the bins such that
(1) I minimize the ratio of the ...
- 115
2
votes
2
answers
142
views
Linear Programming Sensitivity to Matrix
Consider a linear program in the following standard form:
\begin{align*}
&\max c^T x &\\
&\mbox{subject to:}\\
&A x \preceq b\\
&x \succeq 0
\end{align*}
Its dual is
\begin{align*}...
- 575
4
votes
0
answers
138
views
Which variant of the ellipsoid method was used for the Santa Claus problem?
As one of the steps in the article The Santa Claus problem (Bansal and Sviridenko, 2006) the following linear problem was considered (at the end of the second page, as the dual):
\begin{align*}
&\...
- 101
2
votes
1
answer
127
views
Approximating the utilitarian welfare minus a constant
Assume we have $n$ agents and $m$ indivisible goods that need to be allocated among the agents such that their sum of utilities is maximized.
Denote the set of allocations by $\mathcal{A}$ and the ...
- 101
2
votes
0
answers
46
views
Submodulare welfare maximization: is an additive approximation algorithm known?
Sudmodular welfare maximization is the problem of allocating items among agents with different valuations, represented by submodular set functions, such that the sum of agents' values is as large as ...
- 2,294
-1
votes
1
answer
76
views
Find Combinations of fibonacci values to approximate a target value given $F(A,B,C,D) = (A + B + C) / D$
I am able to solve this using brute force but curious if there is a better approach.
Given the function $F(A,B,C,D) = (A + B + C) / D$ where each variable is in the first 7 distinct values of the ...
- 1
1
vote
0
answers
31
views
Optimization: Turning a sparse graph of probabilities into the maximum likelihood DAG
I have a sparse matrix of probabilities that I want to turn into a DAG. If x[m,n] = pr it means that m is a descendent (direct or transitively) of n with probability pr. I want to construct a DAG over ...
- 111
1
vote
0
answers
35
views
Justification of smoothness of component functions
In stochastic optimization, the common objective is to minimize $f(x) = \frac 1N \sum_{i=1}^N f_i(x)$ (there is a different formulation, but it doesn't matter for this question).
For nonconvex ...
- 201
-2
votes
1
answer
297
views
What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?
There is an ever going trend to believe that a large number of NP-Complete or NP-Hard problems can be solved using quantum heuristics.
I have observed, a common trend, to take any sort of ...
- 183
3
votes
1
answer
238
views
Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable
It is known that the problem of integer linear programming is NP-hard, but its fractional relaxation can be solved in polynomial time. The concept of fractional relaxation can be applied to any ...
- 2,294
1
vote
1
answer
139
views
How to calculate processor throughput boundary in CSAPP?
In Chapter 5.7 of CSAPP, author list out the throughput boundary of Intel Core i7 Haswell while executing the operation Integer addition and multiplication, floating points addition and multiplication....
- 11
0
votes
1
answer
207
views
Solving Grouped Weighted Job Scheduling with Release Times and Deadlines on a Single Machine with Multiple Availability Intervals
I'm working on a scheduling problem where I need to schedule a set of n weighted jobs that are partitioned into m groups, where ...
0
votes
1
answer
76
views
An inequality about median of points in higher dimensions
Let $S$ be a set of points in $\mathbf{R^d}$ and let $m$ be the median of this set of points, i.e. $\sum_{x \in S} || x - y||$ is minimized when we have $y=m$. Now let $z$ be an arbitrary point in $\...
- 1
3
votes
1
answer
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
4
votes
0
answers
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
0
votes
0
answers
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
0
votes
0
answers
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
3
votes
1
answer
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
3
votes
2
answers
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
1
answer
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
0
answers
66
views
Unbounded Knapsack Instance with a Single Optimum that takes each Item Once?
Consider the Unbounded Knapsack Problem (UKP): We are given a set of $n$ items $I = \{1,\ldots,n\}$ of integral weights $w_1, \ldots, w_n \in \mathbb{N}$, integral profits $p_1, \ldots, p_n \in \...
- 412
0
votes
0
answers
62
views
Uniformly redistributing items across bins. What problem is this?
I'm trying to find reading material on a particular problem I'm interested in, but I don't know the terms to search.
Problem assumptions/definitions:
We have finite number of items I with weights [0, ...
- 101
1
vote
0
answers
46
views
Will the maximum entropy joint distribution given a known set of marginal distributions have the maximum plausible support?
Define $[n] = \{1, 2, ..., n\}$. Given a distribution $P : \{0, 1\}^{[n]} \rightarrow [0, 1]$ and a subset $S \subseteq [n]$, we can define the $S$-marginal of $P$, $P_S : \{0, 1\}^S \rightarrow [0, 1]...
- 1,582
1
vote
0
answers
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
0
votes
0
answers
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
3
votes
0
answers
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
0
answers
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
0
answers
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
4
votes
1
answer
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
2
answers
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
2
votes
1
answer
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
0
votes
0
answers
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