Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
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$...
0
votes
0answers
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 ...
0
votes
0answers
18 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&...
1
vote
0answers
23 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
0answers
21 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 ...
0
votes
0answers
42 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
1answer
92 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 =...
0
votes
1answer
114 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
0answers
56 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
0answers
40 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 ...
6
votes
1answer
278 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
votes
1answer
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 ...
1
vote
2answers
175 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 ...
3
votes
1answer
149 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 ...
2
votes
1answer
155 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 ...
1
vote
0answers
38 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
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 ...
0
votes
0answers
55 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)$...
4
votes
0answers
45 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
35 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 ...
5
votes
0answers
151 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 ...
6
votes
2answers
369 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_{...
5
votes
1answer
244 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
167 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, ...
1
vote
1answer
92 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
48 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
224 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
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 ...
2
votes
1answer
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.
0
votes
0answers
76 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
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 '...
5
votes
0answers
106 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
114 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
41 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
116 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
39 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 = \{...
1
vote
0answers
138 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
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 ...
3
votes
1answer
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 ...
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}\...
10
votes
1answer
524 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 ...
-1
votes
1answer
63 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
56 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
97 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
87 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 ...

1
2 3 4 5
9