# Tag Info

10

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

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 ...

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)

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 ...

3

No, Bellman-Ford won't work because the problem you described is NP-hard. This is pretty easy to prove. I've been able to come up with several reductions using the same strategy. The general idea is to make it so that in the path you have several sections that can be chosen independently; then the overall question becomes whether you can coordinate all ...

3

Unless $P=NP$, there does not exist a polynomial time approximation algorithm that returns solutions of value at most $\text{OPT}+d$. Suppose otherwise, and consider some fixed $d$ for which there does exist such an approximation algorithm $A$. We construct a new multiplicative polynomial time approximation algorithm from $A$, that always returns solutions ...

2

In Knuth Vol II Theorem E on page 494 he presents an algorithm that can evaluate a polynomial using $\frac{n}{2} + 2$ multiplications. The theoretical minimum is $\frac{n}{2}$, assuming generic polynomials. The algorithm requires factoring polynomials. There is another algorithm from Rabin & Winograd that only requires division, but runs in $\frac{n}{2} +... 2 Some such problems are considered here https://eccc.weizmann.ac.il/report/2014/098/ under the name "simultaneous approximation". See Theorems 1.1 and 1.3. 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 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 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

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

Even if $d = d(n) \le n^{1-\epsilon}$ for an $m \times n$ matrix $A$, no additive approximation $\mathrm{OPT} + d$ is possible unless $\mathsf{P} = \mathsf{NP}$. Let $N = n^k$ for some constant $k$, and take the Kronecker product $A' = I_{N} \otimes A$, and $b' = e_{N} \otimes b$, where $I_N$ is the $N\times N$ identity and $e_N$ is the $N\times 1$ all-ones ...

1

Yes, it is called a multiple-choice knapsack problem. It can be solved in time $O(N B)$ by dynamic programming. The state of the dynamic program is given by a pair $(i, b)$ and the associated value is the maximum value (clicks) you can get with keywords from $1$ to $i$ with a budget at most $b$. Source: S. Martello, P. Toth. Knapsack Problems. Wiley, ...

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