Questions tagged [optimization]
general questions about selecting a best element from some set of available alternatives.
386
questions
0
votes
0answers
31 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 ...
1
vote
0answers
84 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 ...
0
votes
0answers
45 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)$...
3
votes
0answers
44 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 ...
0
votes
0answers
34 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 ...
4
votes
0answers
89 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 ...
2
votes
1answer
34 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 ...
5
votes
2answers
325 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_{...
4
votes
1answer
214 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)\...
2
votes
0answers
152 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
vote
0answers
49 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, ...
0
votes
1answer
65 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 ...
0
votes
0answers
29 views
Optimum partitioning of vertices into mutually disjoint subsets in a weighted graph
tl;dr I'm trying to partition my students into groups with respect to their preferences, i.e. they can declare if they want to be with someone in a group or if they do not want to be with someone in a ...
0
votes
0answers
47 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 ...
3
votes
1answer
216 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}\...
2
votes
0answers
28 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 ...
2
votes
1answer
130 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.
0
votes
0answers
56 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 ...
-2
votes
1answer
145 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 '...
5
votes
0answers
103 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 $...
0
votes
0answers
110 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
0answers
39 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 ...
2
votes
1answer
105 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 ...
1
vote
0answers
35 views
Minimum graph cycle basis respect to non-empty pairwise intersection of cycles
I'm trying to understand the following problem if anyone can help I'll be very grateful
Instance: undirected, unweighted, connected graph graph $G=(V,E)$.
Question: find a minimum cycle basis $B = \{...
0
votes
0answers
112 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 ...
1
vote
2answers
106 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 ...
3
votes
1answer
103 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 ...
4
votes
0answers
84 views
Complexity of finding the mean of the subset with smallest variance
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}\...
9
votes
1answer
497 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 ...
1
vote
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 ...
0
votes
0answers
44 views
Would a machine learning algorithm benefit from an “optimization oracle”?
I'm trying to understand the behavior of machine learning algorithms where the loss function is non-convex and the problem of training the ML on a specific data set is computationally hard.
Now let'...
-1
votes
1answer
62 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 ...
1
vote
0answers
39 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 ...
0
votes
1answer
87 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, ...
5
votes
0answers
84 views
Optimal point placement on integer lattice
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}\...
1
vote
0answers
52 views
Tight estimates on the Lovász and Multilinear extensions of a submodular function
I assume here some familiarity with the jargon used in submodular optimization (please let me know if something is unclear).
Let $f:2^V \to \mathbb{R}$ be monotone, normalized and submodular. For ...
2
votes
0answers
30 views
Finding shortest calculation of the sum of a subset of a group, given sums for other previously summed subsets
Say $S=\{g\in G\}$ is a set of elements in an abelian group $G$ whose group operation $(+)$ is expensive to compute. Given a subset $T\subset S$, we want to compute the sum of $T$'s elements, $\...
0
votes
0answers
89 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$ ...
3
votes
0answers
55 views
Gradient descent step size for strongly convex functions
Suppose we are optimizing a strongly convex function $f(x)$ via gradient descent $x_{t+1} = x_t - \eta_t \nabla f(x_t)$. By strongly convex I mean that $f(x+h) \ge f(x) + \langle \nabla f(x), h \...
0
votes
0answers
84 views
Complexity of multi-objective optimization problems
How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)?
It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the ...
0
votes
1answer
80 views
Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only?
$\DeclareMathOperator*{\argmin}{arg\,min}$Can something be said about the difficulty of minimizing the quantity
$$g(x) = \sum_{i=1}^n\sum_{j=i+1}^n f(x_i, x_j)$$
of some string of symbols $x \in \...
0
votes
1answer
134 views
Dividing a complete graph into two cliques with maximal sum of edge weights
Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\...
0
votes
2answers
452 views
Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums
My scenario has various flavors of SAT, constrained quadratic pseudo-Boolean, and integer programming. My attempts to formalize and solve the problem with Z3's ...
2
votes
1answer
172 views
Sum From A List Of Numbers (Algorithm) [closed]
I came upon a problem and have been trying to find a method more efficient then brute force, but I came up with nothing; and I am not even sure how to approach it...
You have a list of numbers and a ...
2
votes
0answers
211 views
Run Length eXtreme encoded length
In run length encoding (RLE) the code stream consists of pairs $(c_i,\ell_i)$, which is understood as writing the character $c_i$ repeatedly $\ell_i$ times.
Consider the following "improvement" of ...
3
votes
0answers
50 views
AMQ (Bloom-filter like structure) lower bounds
I want an Approximate Member Query structure (that is, something like Bloom filter), but with the highest possible compression ratio. I know that for AMQs where query is done in constant time, the ...
1
vote
2answers
102 views
Embedding a n-tree into a b-dimensional space
Given a (directed) n-tree $T=(N,E,r)$ rooted in $r\in N$, I want to represent each node $n\in N$ at most as a $m$-dimensional vector $v_n\in \mathbb{R}^m$ (From the current Yuri's reply, m cannot be $...
4
votes
1answer
63 views
Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length
If $a_{ij}$ is an $m \times n$ matrix of real numbers, and $b_j$ are $n$ more real numbers, then
$$\max_i \sum_j (a_{ij} x_j + b_j) \qquad (\ast)$$
is a convex piecewise linear function of $(x_1, \...
-3
votes
1answer
118 views
Finding the maximum no. of people who get along in a group [closed]
Suppose that there are 15 people in a room. Assume that each person gets along with other people in the room (but not everyone). (Note that the "feeling is mutual" between any two people who are ...
1
vote
1answer
101 views
Vehicle scheduling
Suppose there are $n$ resources which can do some work. Each resource has a number of time windows: $tw_{i,k}=\{start_{i, k},stop_{i, k}\}$, such that the resource can perform its functions only ...
