Questions tagged [optimization]
general questions about selecting a best element from some set of available alternatives.
415
questions
1
vote
0
answers
46
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 ...
- 557
-4
votes
0
answers
43
views
do while loop optimization
The following method of printing all subarrays(contiguous subsequences) of an array is faster as compared to the general method of using three nested for loops:
...
0
votes
0
answers
25
views
Custom data structure for subarray problems
Is it possible to build a data structure for solving subarray related problems efficiently (E.g. counting the number of subarrays of an array satisfying a given condition)?
4
votes
1
answer
79
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
90
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 ...
- 587
2
votes
1
answer
171
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 ...
- 557
0
votes
0
answers
55
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 ...
- 65
2
votes
0
answers
98
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,
\...
- 1,826
2
votes
1
answer
105
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 \...
- 1,826
2
votes
0
answers
66
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)...
- 217
2
votes
0
answers
61
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$.
...
- 1,826
4
votes
0
answers
92
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- ...
- 10k
0
votes
0
answers
94
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
110
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
146
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,378
3
votes
0
answers
96
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 ...
- 1,826
0
votes
0
answers
44
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 (...
- 557
1
vote
1
answer
55
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$...
- 57
0
votes
0
answers
51
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 ...
0
votes
0
answers
24
views
Fast algorithms for convex-convex quadratic fractional programming
What are the fastest algorithm(s) (possibly approximation algorithms) for solving convex-convex quadratic fractional programming problems, i.e. optimization problems of the form
$$
\begin{align*}
\sup&...
- 304
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
22
views
Going from one base packing to another using basis exchanges
Suppose I have a matroid $M = (E, \mathcal{I})$. It is a known fact that given any two bases $X_0$ and $X_n$, we can transform $X_0$ into $X_n$ by repeatedly applying the basis exchange axiom. So ...
- 557
0
votes
0
answers
45
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 ...
- 1,826
1
vote
1
answer
101
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 =...
- 557
0
votes
1
answer
160
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 ...
- 557
0
votes
0
answers
88
views
Examples of SDP constant approximation algorithms on minimisation problems
I was recently going through a survey on semidefinite programming and its use in approximation algorithms. Here are some problems I am familiar with that have SDP approximations:
Max Cut ($\approx 0....
- 680
1
vote
0
answers
41
views
Modifying sets to minimize the distance among each pair of the mean value of sets
Given $n$ points, each point $x_i$ has a value $v_i \in \mathbb{R}^{d}$, and there are $m$ point sets $\{S_1,\dots, S_m\}$ that each point set consists of some points. The size of point sets can be ...
- 57
7
votes
1
answer
287
views
Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries
My question concerns the NP-hardness of the following discrete optimization problem:
Given a matrix $A \in \{ \pm 1 \}^{m\times n}$,
$$\begin{array}{ll} \underset{x \in \{ \pm 1 \}^m ,\, y \in \{ \pm ...
- 73
-2
votes
1
answer
315
views
Find research partner (profession and beginner)
I've 10 years of industrial work, but in my free time, I do research, write papers to conferences, help to teach to my old friend at the university and I even did a Ph.D. full-time program.
Now, I've ...
- 45
1
vote
2
answers
198
views
Finding the point that maximizes a linear function
Consider $N$ two-dimensional points of the form $(x_i, y_i)$ where all $x_i, y_i > 0$ are positive integers. We will be given a workload of queries $Q = \{c_1, \dots, c_k\}$ where for each $c_j \in ...
- 1,015
3
votes
1
answer
153
views
TSP with "enemy" nodes
I am curious if the following variation of the traveling salesman problem (TSP) (or a vehicle routing problem (VRP) version) occurs in the literature and has a name I could search for.
The story/idea ...
- 407
2
votes
1
answer
170
views
Characterization of integral polyhedra
A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$.
Equivalently, $P$ is integral if ...
- 557
1
vote
0
answers
45
views
program search with optimization methods for (resource bounded) Kolmogorov complexity
Are there fields of research that look at finding short programs for generating strings (therefore trying to find the (resource bounded) Kolmogorov complexity of the string), but using optimization ...
- 21
1
vote
0
answers
86
views
Is there a "common" name for this type of combinatorial optimization problem?
I'm trying to find papers that discuss approaches (in particular, any Deep Learning or Deep Reinforcement Learning techniques) that could be used used to solve the problem described in the next ...
- 11
0
votes
0
answers
73
views
Prove that this linear relaxation has half-integral extreme points
Given a graph $G=(V,E)$, here is a Linear Relaxation of the edge cover polytope:
(1) For each $v \in V, \sum_{e \in \delta(v)} x_e \geq 1.$
(2) For each $e \in E$, $0 \leq x_e \leq 1.$
Here $\delta(S)$...
- 557
4
votes
0
answers
46
views
Minimal partition covering?
I am working on a problem that arises in the design of experiments. I wonder if it is part of a well-studied class of problems.
The problem is:
Start with a set of points $S$ and a target partition of ...
- 141
0
votes
0
answers
36
views
Convergence of first order subgradient methods for non-convex functions
This lecture note gives the proof for how deterministic subgradient method converges on non-smooth convex and strongly convex Lipschitz functions.
Is there a non-convex version of this proof?
Like ...
- 1,443
5
votes
0
answers
170
views
Minimum spanning tree, but with an unusual objective function
This is a problem that came up in my study of rumour networks. I was wondering if anyone had thoughts or references on this problem.
If we have a rooted tree $T = (V,E)$ with root $r$, I first label ...
- 557
2
votes
1
answer
39
views
Maximum weight matching with classes of edges in a multi-edge bipartite graph
Posted a similar question in mathoverflow, have tried to reduce this to Ford Fulkerson, but been stuck. Thought I'd ask TCS community to see if there are any ideas from individuals, here.
Consider a ...
- 23
6
votes
2
answers
455
views
Is that edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{...
- 533
6
votes
1
answer
289
views
Is this edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\...
- 533
2
votes
0
answers
208
views
Is this node permutation optimization NP-Hard?
Let $G=(V,E)$ be an undirected graph and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{succ}_{\pi}(v)$ the set of neighbors of $v$ that occur after $v$ in ...
- 533
1
vote
0
answers
51
views
Does a decision oracle imply an algorithm for $\mathbb{NP}$ - hard problems with several parameters?
If we consider the decision version of the classical graph coloring problem, then we have some graph $G$ and some integer $k$ and we want to color $G$ with at most $k$ colors. It is well known that, ...
- 11
1
vote
1
answer
154
views
Knapsack problem with dependent weight and profits among the items
I'm working on a problem that may be reduced to the following variant of multiple knapsack problem:
Each knapsack has its own valuation function; an item brings different profit and weight to a ...
- 11
0
votes
0
answers
54
views
A variant of randomized co-ordinate descent
Let us consider the following optimization problem.
$\mathcal{P} =\{P_1,\cdots,P_n\}$, where $P_i\subset\mathbb{R}^d$. Let $m = max_i\lvert P_i\rvert$. The goal is to find a point $c$ such that ...
- 267
3
votes
1
answer
229
views
An optimization problem
I am considering the following optimization problem. Let $P$ be a set of $n$ points in $\mathbb{R}^d$
maximize $\sum_{p\in P}\vert\langle \Vert p\Vert p, \hat{x}\rangle\vert$ subject to $\Vert\hat{x}\...
- 267
2
votes
0
answers
32
views
Complexity of best folding of a 2D set (or how to optimize a sandwich)
Motivation:
I was making lunch for my son, part of which is making a sandwich from two halves of a slice of bread. In order to minimize the parts of bread that have cheese on them, and are not covered ...
- 5,261
2
votes
1
answer
155
views
Is this homework problem on T-joins wrong? [closed]
In Question 9.3a, it states that if $T=V$, then the minimum cost perfect matching is the minimum cost T-join. Is this actually true? I think I have a counterexample which I have drawn below.
- 557
-2
votes
1
answer
160
views
How to calculate complexity in a high dimensional space?
Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong.
For a specific f(), I'm defining a term '...
- 55
5
votes
0
answers
152
views
Exact algorithms for $k$-means
Lets recall the definition of $k$-means clustering for euclidean spaces.
Let $X$ be a set of $n$ points in $R^d$ and $k$ a given natural number. Let $C$ any $k$ clustering of $X$. Define the cost of $...
- 181