# Questions tagged [optimization]

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

427 questions
Filter by
Sorted by
Tagged with
41 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 ...
560 views

• 553
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 ...
• 553
1 vote
52 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
202 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
61 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 ...
• 266
232 views

• 181
120 views

### Algorithms and approximations for optimal offline binary tree operations

Let's say we are using a binary tree to represent a set of elements, with operations $\mathsf{insert}(x)$ and $\mathsf{delete}(x)$. We will assume that the operations are used such that a deleted ...
1 vote
52 views

### Additive welfare maximization under matroid constraints

In the welfare maximization problem, there is a set $[m]$ of items, and $n$ functions $w_i: 2^{[m]} \to \mathbb{Z}_+$. The goal is to partition the items into $n$ subsets $S_1,\ldots,S_n$ such that ...
• 1,850
148 views

### Compiling einstein sums optimally

Einstein summation is a convenient way to express tensor operations which has found its way in tensor libraries like numpy, torch, tensorflow, etc. Its flexibility lets us represent the product of ...
• 419
1 vote
49 views

• 181
566 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 ...
• 553
1 vote
87 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 ...
• 241
77 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 ...
• 103
1 vote
75 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 ...
• 1,921
1 vote
155 views

113 views

### NP-Hard Knapsack Instances

Consider the classic Knapsack optimization problem (KP): Given $p_1, \dots, p_n, w_1, \dots, w_n, B\in\mathbb N$, compute a solution $I\subseteq \{1,\dots,n\}$, such that $\sum_{i\in I} w_i \leq B$ ...
• 141
85 views

• 690
188 views

• 175
66 views

• 1,850
170 views

### Minimum relevant variables in linear system - additive approximation

In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.: $$A x = b$$ and the goal is to find a solution $x$ with as few nonzero variables as ...
• 1,850
1 vote