The 2024 Developer Survey results are live! See the results

# Tag Info

Accepted

### Is there a counterexample to this work?

Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first ...
• 5,782
Accepted

### Anti bin packing

This problem is called bin covering. It's NP-hard and hard to approximate to better than a factor of two by an easy reduction from subset sum but has an asymptotic approximation scheme (i.e. one that ...
• 51.1k
Accepted

### What are some example problems for integer programming that are *not binary*

Here are a few examples: (Most Common) Cutting Stock Problem - determine patterns for which to cut boards in order to meet demand. (Kinda same problem) - Knapsack with general integer variables - ...
Accepted

### Consequences of faster parameterized integer programming

An instance of CNF-SAT with $k$ variables can easily be written as a 0/1 integer linear program over the same variable set, since a clause such as $x_1 \vee x_3 \vee \neg x_4 \vee \neg x_6$ naturally ...
• 5,275
Accepted

### Characterization of integral polyhedra

Here's a proof (sketch) that doesn't explicitly use duality. More precisely, it replaces duality by a seemingly weaker (and hopefully easily believable) geometric fact, in Step 3 below. EDIT: But, ...
• 10.9k
Accepted

### Fixed parameter tractable Integer Programming and $FPP$

You're confusing decision problems (in the classical sense) with parameterized decision problems. Classical decision problems are subsets of $\Sigma^*$, whereas parameterized decision problems are ...

### FPT algorithm for mixed integer program

The complexity of Lenstra's algorithm for mixed-integer programming in his paper runs as $2^{O(n^3)}*poly(d, \phi)$ where there are $n$ integer variables, $d$ continuos variables, and $\phi$ is the ...

### On integer programming

It's NP-hard. Given an integer programming problem $P$, add an irrelevant variable $z$ with no constraints; call the resulting problem $P'$. Now if $P$ has no solutions, then $P'$ has no solutions; ...
• 12.3k
Accepted

### On integer programming

(1) As finding a second satisfying assignment to a 3SAT formula is still $\mathsf{FNP}$-complete (indeed, it is $\mathsf{ASP}$-complete, see Theorem 3.5 of [1]), and we can encode 3SAT as an integer ...
• 37.8k

### Have fixed parameter integer program algorithms ever been implemented for research use?

The original algorithm of Lenstra (from 1983) has not been implemented AFAIK. Certainly, no open-source code is known to be available. Lovasz and Scarf proposed (in 1992) a generalized basis ...
• 326

### Is that edge orientation optimization problem NP-hard?

Summary OP's problem has a polynomial-time algorithm via reduction to min-cost bipartite matching. (Lemma 1, below.) Alternatively, one can strengthen OP's relaxation QP directly, by modeling the ...
• 10.9k
Accepted

### Is this edge orientation optimization problem NP-hard?

I believe that this problem is NP-hard, here is a sketch proof (don't hesitate to ask for more details if needed). The idea is based on a reduction from the Not-all-equal 3-SAT. For $\varphi$ a 3-SAT ...
• 775

### Is that edge orientation optimization problem NP-hard?

Definition: Given an undirected graph $G$ and an edge orientation $\vec{G}$, an unstable path is a directed path that goes from a node $s$ to a node $t$, such that the out-degree of node $s$ is ...
• 775
Accepted

### How hard is this combinatorial optimisation problem?

This problem can be solved with dynamic programming in pseudo-polynomial time (proof below). Therefore, it is not possible to show that this problem is strongly NP-hard (unless P=NP). First, let's ...
• 2,873
Accepted

### Minimum Union-Sum Cost Path

EDIT (Jan 2019): Lemma 2 as currently stated below is wrong. (Indeed, given any instance, adding a single edge with a single type of very large cost will not change the instance but will yield $N(I)=1$...
• 10.9k

### Which Integer Linear Programs are easy?

An integer program with only equalities can be solved by linear program.
• 13.1k
Accepted

### Ensuring integral maximizer from integral linear program

Given an integral LP, you can use a LP algorithm to compute in polynomial time the optimal value of the LP, a vertex of the feasible region (polytope) of the LP where the optimal value is attained. ...
• 18.2k

### Name of (and solution to) this generalization of linear assignment

It looks to me like this is a special case of minimum cost flow; introduce one vertex per row and one per column, with an edge for each entry whose cost is the negative of the value of that entry and ...
• 12.3k
Accepted

### Integer programming: enforce the constraint that a subgraph contains at most $k$ connected components?

Base on Komus's constraint, we add another constraint which ensures a Steiner Tree on $G^{'}=(V, E^{'})$, where $E'=\{(i,j): i,j \in V\}$: \sum_{e \in cut(U,V)}x_e \ge 1, \forall u,v \in T, \forall ...
• 483
Accepted

### Hardness of computing the dimension of an integral polytope?

Yes, MORE-SAT, defined below, is one example of a combinatorial optimization problem for which the natural 0/1 integer linear program (ILP) is guaranteed to be feasible, and determining the dimension ...
• 10.9k
Accepted

### Do there exist two equivalent objective functions one of which can be approximated but another one cannot?

The answer to Question (1) is no. The answer to Question (2) is yes. Here are the details. I'll work with the following equivalent problem formulations. For the input, we are given $n$ pairs of ...
• 10.9k
1 vote

### Is that edge orientation optimization problem NP-hard?

Note that the related problem pointed in the motivation of the original post is NP-hard. The proof is available in the Annex B of this paper: https://arxiv.org/pdf/2203.04774.pdf
• 121
1 vote

### How do minimally violated k-mod cuts work (intuitive explanation)?

Suppose you have an integer linear program, and it contains the following constraints: x1 + x2 + x3 >= 1, x1 + x2 + x4 >= 1, x1 + x3 + x4 >= 1, x2 + x3 + x4 >= 1. If we set x1, ..., x4 to 1/3, we ...
1 vote

### Max weight travel on a graph with deadline

Since you specifically ask later about the version of the problem in which the given path is restricted in how many times it visits each vertex/edge, I assume that the original version of the problem ...
• 2,873
1 vote
Accepted

### Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K

When the costs are all equal, you are looking for the fewest number of edges to bring your graph to being of at most diameter $k$. This is the graph diameter augmentation problem. You are looking for ...
• 1,318
1 vote

### How fast can we solve a totally unimodular integer linear program?

It has been shown that totally unimodular LP is solvable in strongly polynomial time under a "degeneracy assumption" - link here (thus if the ILP has a Totally Unimodular (TU) formulation with the ...
• 1,261

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