Questions tagged [optimization]
general questions about selecting a best element from some set of available alternatives.
440
questions
0
votes
0
answers
23
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
113
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
132
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*}
&\...
- 91
1
vote
1
answer
82
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 ...
- 91
2
votes
0
answers
43
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,078
-1
votes
1
answer
74
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
21
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
30
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
219
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
224
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,078
0
votes
1
answer
49
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....
- 1
0
votes
1
answer
142
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
210
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 ...
- 91
3
votes
0
answers
58
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,078
0
votes
0
answers
95
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,078
0
votes
0
answers
155
views
When does the 'Overlap Gap' property not hold?
The overlap gap property describes problems where good solutions form clusters, so that 2 good solutions are either very close or very far. Problems having this property are problematic for ...
0
votes
0
answers
34
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. ...
- 653
3
votes
1
answer
192
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
221
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
81
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
91
views
How to solve the following continuous optimization problem?
Consider a function $f: X\times Y\times N$, where $X, Y \subseteq \mathbb{R}^m$ are convex sets, and $N = \{1,2,\dots,n\}$. We additionally know that
$f(\cdot,y,S)$ is convex for fixed $y,S$
$f(x,\...
- 25
1
vote
0
answers
65
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 \...
- 173
0
votes
0
answers
57
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,572
1
vote
0
answers
80
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,367
0
votes
0
answers
26
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
74
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,151
1
vote
0
answers
55
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)$...
- 607
1
vote
0
answers
60
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 ...
- 607
4
votes
1
answer
187
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
98
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 ...
- 617
2
votes
1
answer
205
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 ...
- 607
0
votes
0
answers
75
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 ...
- 95
2
votes
1
answer
134
views
Optimization problems where the solver can choose which variables are continuous
A typical optimization problem looks like the following, where $f$ represents the objective and $g$ the constraints:
$$
\text{maximize}~~~f(x1,\ldots,x_n)~~~\text{subject to}:
\\
g(x_1,\ldots,x_n)=0,
\...
- 2,078
3
votes
1
answer
155
views
Is there an approximate version of the strong duality theorem for linear programming?
Consider the following dual linear programs:
$$
\min \mathbf{c^T x} ~~ \text{s.t.} ~~ A \mathbf{x} \geq \mathbf{b}, \mathbf{x}\geq 0;
\\
\max \mathbf{b^T y} ~~ \text{s.t.} ~~ A^T \mathbf{y} \leq \...
- 2,078
2
votes
0
answers
108
views
Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?
Given a graph $G=(V,E)$, costs $c \in \mathbb{R}^E$ the TSP problem is to compute a min cost tour of the graph. The LP is
min $ c^tx $
$x(\delta(S)) \geq 2 \ \ \ \ \forall S \subset V $
$x(\delta(v)...
- 186
2
votes
0
answers
106
views
Can this relaxed subset-sum problem be solved with a smaller dynamic program? [closed]
Cross-post from CS.SE
In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$.
...
- 2,078
4
votes
0
answers
101
views
Analogue of Chow-Liu tree for $L_1$
Say $\Omega$ is a finite set and $f$ a probability mass function (pmf) over $\Omega^d$. Now let $T$ be a spanning tree on the set $V=\{1,2,\ldots,d\}$, and consider a collection of one- and two- ...
- 10.3k
0
votes
0
answers
138
views
optimization on graph edges selection
I have the below problem. I wonder if there exists a similar known class of problems (e.g., in optimization, graph theory) which I can relate my problem to, and find a similar solution there.
I am ...
- 1
1
vote
1
answer
161
views
3-SAT runtime if an optimal order to eliminate possible solutions is known
As a mental exercise I have been playing around with the 3-SAT problem, but I am having difficulty proving or disproving the usefulness of a current idea that I am playing around with.
My current ...
8
votes
0
answers
151
views
What is the least compressible probability distribution? (under entropy constraint, for an expected squared error metric)
Consider a distribution $\mathcal D$ over the reals, a real parameter $H\in\mathbb R^+$, and an integer parameter $k\in\mathbb N$.
The Entropy-Constrained Quantization problem asks what is the best ...
- 9,438
3
votes
0
answers
160
views
Bin packing where each item must occur in $k$ bins
I am looking for information on a generalization of bin-packing in which each item should appear in exactly $k$ different bins, for some positive integer $k$. The standard bin packing problem ...
- 2,078
0
votes
0
answers
51
views
Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?
The TAP problem and the CacAP problem can be seen as covering problems for the minimum cuts of a graph.
It seems like these problems would fall under the framework of network design problems (...
- 607
1
vote
1
answer
61
views
Maximize the absolute value of connected nodes after $k$ modifications
Given a graph $G=\{V,E\}$, each node $i$ has a value $v_i$. Given budget $k$, we have $k$ chance to add 1 or minus 1 for a node's value, for example, $v'_i=v_i+1$ or $v'_i=v_i-1$. In particular, $v'_i$...
- 67
0
votes
0
answers
55
views
Finding the best $k-$subset which maximizes a matrix sum
Let $M\in \mathbb{R}^{N\times N}$ be a given matrix and $k\ge 2$ be a given integer. Then my question is the following optimization problem:
Is there a polynomial-time solution to the following ...
1
vote
0
answers
32
views
Reference showing global optimality of local minima for matrix factorization
Consider the following matrix factorization problem: Given an $n\times m$ matrix M, find $n\times r$ and $m\times r$ matrices $U$ and $V$ such that $||UV^T - M||_F^2$ is minimized.
I have heard it ...
- 111
0
votes
0
answers
57
views
Using bin-packing algorithms to approximate maximum-makespan
Bin-packing (BP) and maximum-makespan (MM) are dual problems. In both problems, the input can be defined as a set $S$ of positive integers, and the output is a partition of $S$.
In BP, there is a ...
- 2,078
1
vote
1
answer
136
views
Partition the edges of a bipartite graph into perfect $b$-matchings
Any $r$-regular bipartite graph can be partitioned into $r$ disjoint perfect matchings.
I want to know whether a version of this extends to perfect $b$-matchings.
Suppose we have a bipartite graph $G =...
- 607
0
votes
1
answer
220
views
Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?
Often, we can model combinatorial optimization problems with an Integer Program. Then there is an associated Linear Relaxation which drops the integrality constraints on the variables.
Let's say we ...
- 607