# Questions tagged [optimization]

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

402 questions
Filter by
Sorted by
Tagged with
30 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 (...
51 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$...
48 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 ...
20 views

230 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 ...
175 views

246 views

30 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 ...
135 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.
78 views

### Graph-based backjumping vs Conflict-based backjumping comparison in CSP

Graph-based backjumping vs Conflict-based backjumping in CSP I have been studying techniques to find solutions in backtracking to model and solve a problem in c++ with this methods and I have the ...
148 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 '...
106 views

139 views

### Is the matching polytope integral?

In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf they prove the integrality of the matching polytope using the integrality of the perfect matching polytope. The ...
107 views

### Where to find info on (polytime) approximability of various discrete optimization problems?

Where to find info on (polytime) approximability of various discrete optimization problems? Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of ...
104 views

### Parametrized complexity of sparse optimization

Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||_0\le k$ are known to be NP-hard. [Actually, I just realized that I don't have a reference, so ...
Let $x_1,\ldots, x_n \in R^d$, and $\alpha \in (0, 1)$. Suppose that $\alpha n$ is an integer. Let's consider the following problem $\min_{\mu \in R^d} \frac{1}{n} \sum_{i=1}^n F\left(\frac{\pi(i)}{n}\... 1answer 526 views ### Is the following graph optimization problem approximable within a constant factor? 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{pred}_{\pi}(v)$(respectively$\text{succ}_{\pi}(v)$) the set of ... 1answer 86 views ### Name of (and solution to) this generalization of linear assignment I would like to know if the following problem is known and has any efficient solution. Given an$n\times n$score matrix$S$. Find the best$a$elements, in terms of their sum of scores, such that no ... 1answer 65 views ### Is it possible to approximate the solution of NP-Hard problems in polynomial time using linear programming? [closed] Suppose we have a NP-Hard problem such as the k-col, which is meant to determine if a graph may be colored using at most ... 0answers 59 views ### Are the intermediary sets in maximum cardinality search optimal in some way? The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph$G = (V, E)$where$w(u, v)$denotes the weight of the edge$\{u, v\}$, we select a start node$a \in V$and do ... 1answer 98 views ### Finding the size$k$subset in a metric space that maximizes the min distance between elements I have a metric space$(X,d)$and I'd like to find a subset of size k of far away elements. We can cast this as the following optimization problem$\max_{S \subseteq X, |S| = k} ( \min_{i \not = j, ...
What is known about the following point placement problem? For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute \begin{eqnarray*} \mu_1(N,n)\triangleq\min_{\mathcal{P}\...