Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with combinatorial-optimization
Search options not deleted
user 2233
Combinatorial optimization typically deals with optimizing over a finite set of objects that have some combinatorial structure (e.g. trees, matchings, matroids). Approximation algorithms, polyhedral methods, and integer programming are all on topic.
1
vote
Accepted
How to prove the local search algorithm can find the maximum weight independent set in a mat...
Let $I$ be the independent set of size $k$ returned by the local search algorithm. Thus, $c(J) \leq c(I)$ for every independent set $J$ of size $k$ such that $|I \Delta J|=2$. Towards a contradictio …
- 32.1k
4
votes
Partitioning a set of lattice points in the plane into rectangles
Here is a generalization of the original puzzle that also satisfies conditions (1) and (2). Let $k, \ell,n \in \mathbb{N}$, and $S$ be the set of lattice points contained in the convex hull of $\{(-\ …
- 32.1k
11
votes
Accepted
A discrete optimization problem related to the AM-GM inequality
This was essentially answered by Nate in the comments, but here are some more details. As Nate argues, $|m_i - m_j| \leq 1$ for all distinct $i,j$. Thus, if $s=ak+r$, where $a,r \in \mathbb{N}$ and …
- 32.1k
2
votes
A certain instance of the Set Covering problem
For the variant that $\mathcal{P}$ consists of all paths, the problem is equivalent to minimum vertex cover, and hence is NP-complete. To see this, I assume that single vertices do not count as paths …
- 32.1k
1
vote
How does this algorithmic proof of Edmonds-Gallai work?
Here is another approach that fails for a different reason. Perhaps the two failures can be merged into success, but I have not thought about this too deeply.
It suffices to prove the claim for shri …
- 32.1k
10
votes
Accepted
Unique way to partition into two parts of equal weight
The answer is yes. Consider the sequence
$100, 200, 201, 202, 500, 601, 700, 701, 801, 1000, 1194, 1200.$
It is easy to see that $X=\{1,2,5,7,10,12\}$ and $Y=\{3,4,6,8,9,11\}$ are exact. Moreover …
- 32.1k
3
votes
Is the max of two supermodular functions supermodular?
I think the answer is no. Let $f$ be a supermodular, non-negative and increasing (in both arguments) function satisfying $f(0,0)=1, f(0,1)=2, f(1,0)=3$, and $f(1,1)=4.5$. Let $g$ be defined as $g(x, …
- 32.1k
1
vote
Accepted
Partitioning vertex set to maximize weights of inter-class edges?
This is the weighted MAX CUT problem, and it is NP-hard to compute exactly. Note that the case of $\{0,1\}$-weights corresponds to computing a MAX CUT in an arbitrary graph. This later problem has a …
- 32.1k
20
votes
Menger's theorem via matroids
There is indeed a Menger's theorem for matroids first proven by Tutte. The reference is
Tutte, W. T., Menger’s theorem for matroids, Journal of Research of the National
Bureau of Standards—B. M …
- 32.1k
10
votes
Accepted
Menger's theorem with restrictions on where the paths can begin and end
There is no known necessary and sufficient condition like in Menger's theorem.
However, there is a polynomial-time algorithm that decides if the paths exist. This is one of the main results of the Gr …
- 32.1k
6
votes
Accepted
Graph combinatorial optimization problem
The answer is $k=n-2$. To see this, first note that $k \geq n-2$, since the complete graph on $n$ vertices minus an edge has the desired property for $k=n-3$. For the other inequality suppose that $ …
- 32.1k
3
votes
Accepted
Induced matching number
It is unlikely that a nice characterization exists because the problem of computing the size of a maximum induced matching is a well-known NP-hard problem, even for bipartite graphs (as mentioned by P …
- 32.1k
7
votes
Accepted
NP-hardness of finding maximum of minimum element in diagonal of a matrix
This seems to be polynomial. Here is a proof. It will be convenient to regard $A$ as an edge-weighted complete bipartite graph $G$. Let $m_1 < \dots < m_\ell$ be the list of edge weights of $G$, le …
- 32.1k
7
votes
Partition of a graph into subgraphs with small maximum degree
Yes, every graph $G$ with maximum degree $\Delta$ can be partitioned into $k$ sets $X_1, \dots, X_k$ such that the maximum degree of $G[X_i]$ is at most $\lfloor \Delta / k \rfloor$ for all $i$. This …
- 32.1k
1
vote
Maximum subgraph edge distance greater than given number
Your problem is not polynomial (unless P=NP), because your problem is polynomially equivalent to maximum independent set, which is NP-hard.
In one direction, given an edge-weighted graph $G$ and a …
- 32.1k