10

Fixed Point Logic $+$ Counting (FPC) is believed to capture most of the $P$ solvable problems. Anderson, Dawar and Holm 2015 [1]showed that optimization of linear programs is expressible in FPC. Dawar and Wang 2016 [2]showed that The FPC implementation of the ellipsoid method extends to semidefinite programs (subject to some technical conditions).


4

The problem is NP-Complete even for integer values. You can look up the "knapsack problem" to see why. A pseudo-polynomial algorithm exists if you can map your N values to integers (if the number of decimal places are bounded by some constant)


4

Introduce variables $y_{hi}$ together with constraints $y_{hi}=\sum_j (a_{hij} x_j + b_{hj})$ for all $h$ and $i$. Introduce variables $z_h$ together with constraints $z_h\ge y_{hi}$ for all $h$ and $i$. Then minimize $\sum_h z_h$. The resulting linear program can be solved in time polynomially bounded in $\ell, m, n$ and the logarithm of the largest cost ...


3

Your problem is NP-complete, even in two dimensions. There is a straightforward reduction from MINIMUM MAXIMAL MATCHING in bipartite graphs: MINIMUM MAXIMAL MATCHING in bipartite graphs INSTANCE: a bipartite graph $G=(V_1\cup V_2,E)$ with $E\subseteq V_1\times V_2$; an integer $k$ QUESTION: Does $G$ possess a maximal matching $E'$ of cardinality at ...


3

Your problem is at least as hard as the NP-hard problem called Minimum Feedback Arc Set. Consider a directed graph and set $f(u,v)=1$ if it contains an arc from $u$ to $v$, and $0$ otherwise. Then your problem corresponds to finding a minimum feedback arc set: a minimum set of arcs whose removal yields a directed acyclic graph (DAG). From such a DAG, one ...


3

I'm going to assume you didn't mean to end up two (maximal) cliques, but instead two disconnected complete graphs. Those are not the same, e.g. for $n = 6$ you can end up with extra edges that don't form any other maximal cliques otherwise: If that assumption is correct, your operation is called a bisection of the graph. You want to maximize the remaining ...


3

Your problem is the same as optimizing the total time, since you always have to spend $\sum_{i} d_i + s_i$. The optimal solution is drive to the next resource, wait till the next time window that allows the resource to perform its function, let the resource perform its function and repeat. I suggest you start with the following paper, and see if there are ...


2

Convert your array to a zero-one array where $a_{ij}=1$ if persons $i,j$ get along, else it is zero. Let this be the adjacency matrix of an undirected graph $G$ where the vertices are the persons in your formulation. What you are asking about is how to find the maximal cliques (maximal connected subgraphs) of $G.$ This is in general a very difficult ...


1

It's certainly possible to simplify the presentation: A graph $G = (V, E)$ A weight function $w_1 : V \mapsto \mathbb{N}$ A weight function $w_2 : E \mapsto (\mathbb{N} \cup \{-\infty\})$. This corresponds to your formulation of $w_2$ as a total function on $V \times V$, where $w_2(x,y) = 0$ if $(x,y) \notin P$, except that $w_2(x,y) = - \infty$ if $(x, y) \...


1

Can this be reformulated as follows (careful, I am sleep-deprived with a cranky toddler in the room): We are looking at a random graph $G$ with 6000 weighted nodes, a subgraph $G'$ induced by about 4000 edges, and 140.000 other weighted edges of positive weight but strictly smaller than the nodes they connect to. A satisfying assignment for $C$ induces a ...


1

This is not possible if the dimension $m$ is fixed. Consider a complete $b$-ary tree, in which all edges are oriented from the root $r$. Then all vertices lie in a ball of radius $h$ around $v_r$. On the other hand, the distance between every two leaves is greater than $h$. Since there are $N = b^h$ leaves, we get that there are $N$ points in a ball of ...


1

Great intuitive explanations above by Sasho Nikolov and Neal Young. Here's another one Eden Chlamtáč emailed in: Well, the intuition is that the SDP solution assigns greater weight in the objective function to edges whose endpoints that are placed farther apart in the vector solution, so it makes sense to cluster the set of vertices geometrically into two ...


1

To improve gzip compression, you want "similar" strings to be close in the list. There are a number of ways to define such a similarity; let me describe a reasonable one that works well in practice. Recall that gzip's block size is 64K. Thus, your data will be split into blocks of 64K bytes and every block will be compressed independently. Tho optimize ...


1

Here is what you are looking for. It is quite new: https://arxiv.org/pdf/1810.07362.pdf


Only top voted, non community-wiki answers of a minimum length are eligible