Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
8 votes
3 answers
560 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_{...
2 votes
1 answer
253 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 ...
-1 votes
0 answers
17 views

Looking for paper on approximating TSP by cycle covers

I'm looking for a paper about approximating TSP by cycle covers mentioned here https://youtu.be/LPKHnPeF7aI?t=2001 I think he said a name but I couldn't make it out.
0 votes
0 answers
26 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. ...
3 votes
1 answer
161 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 - ...
3 votes
2 answers
208 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)$, ...
0 votes
1 answer
70 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 ...
1 vote
0 answers
83 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,\...
1 vote
0 answers
47 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 \...
0 votes
0 answers
53 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, ...
1 vote
0 answers
43 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]...
0 votes
0 answers
17 views

Why training a GAN with simultaneous optimization of the loss functions does not ensure good images?

I am training a GAN in which I am optimizing or reducing the loss of the generator and the discriminator simultaneously. However, the images generated are very noisy. What could be the hidden reason? ...
23 votes
2 answers
3k views

computing the minimal NFA for a DFA

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known ...
1 vote
0 answers
68 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 ...
0 votes
0 answers
25 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 ...
3 votes
0 answers
71 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 ...
0 votes
0 answers
99 views

In the Schönhage-Strassen algorithm for integer multiplication, when we calculate the product of two n-bit integers, why do we do so modulo 2^n + 1?

I ask this because it seems to me that there might be a loss of information here. The product of two n-bit integers could be up to 2n bits long, but any element of the integers modulo 2^n + 1 is at ...
4 votes
1 answer
1k views

Knapsack with dependent profits (pairs of items)

I'm working on a problem which MAY be reduced to the following version of Knapsack: Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in ...
1 vote
0 answers
53 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)$...
9 votes
3 answers
3k views

How/Why are linear systems so crucial to computer science?

I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network ...
1 vote
0 answers
57 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 ...
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)?
2 votes
1 answer
190 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 ...
4 votes
1 answer
101 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
95 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 ...
2 votes
0 answers
102 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, \...
0 votes
0 answers
63 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 ...
7 votes
2 answers
585 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....
2 votes
1 answer
121 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 votes
0 answers
80 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)...
2 votes
0 answers
84 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 votes
1 answer
317 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 ...
4 votes
0 answers
95 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- ...
0 votes
0 answers
101 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 vote
1 answer
122 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
148 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 ...
2 votes
2 answers
2k views

Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?

There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum algorithm. I understand that the advantage of quantum annealing as ...
3 votes
0 answers
118 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 ...
0 votes
0 answers
47 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 (...
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$...
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 ...
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 ...
0 votes
0 answers
47 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 vote
1 answer
123 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 =...
21 votes
1 answer
3k views

Solving semidefinite programs in polynomial time

We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (...
0 votes
1 answer
169 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 ...
0 votes
0 answers
95 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....
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 ...
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 ...
1 vote
2 answers
213 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
2 3 4 5
9