Skip to main content

All Questions

Filter by
Sorted by
Tagged with
3 votes
1 answer
154 views

How to maximize the variance of a subset of integers?

$\DeclareMathOperator{\Var}{Var}$Given the set of numbers $\Omega := \{1, \ldots, n\}, n \in \mathbb{Z}^+$, how can I choose a subset, $A$ of $\Omega$ , such that $\min(\Var(A), \Var(\Omega \setminus ...
Hasan Zaeem's user avatar
1 vote
0 answers
29 views

Integral hull of a polyhedron Q is polyhedron

Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
Sowbarnika R's user avatar
5 votes
1 answer
424 views

What is the LP gap of vertex cover in planar graphs?

What is the LP gap of vertex cover in planar graphs? The LP I refer to is min $\sum_{e \in E } c_e x_e \ \ $ subject to $ \ \ x_v + x_u \geq 1 \ \ \ \forall uv \in E $ $ c_e \geq 0 $ are ...
Hao S's user avatar
  • 111
1 vote
1 answer
206 views

Show $0-1$ Knapsack is polynomially reducible to this problem

I have already posted this question here but have not received an answer so I am cross-posting with hope to reach a larger amount of mathematicians: Let $T=\{1,\cdots,n\}$ and consider the ...
Kuifje's user avatar
  • 225
1 vote
0 answers
1k views

Number of different combinations in a 0-1 knapsack problem with integer weights [closed]

My question is actually very similar to this other one: Given a vector of positive integers, count the number of combinations which have a sum that produces a different value. But, since this previous ...
Vicent's user avatar
  • 153
2 votes
1 answer
426 views

Network flows with shared capacities

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as: $$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$ where $f(1, 2)$ denotes the flow through arc $(1, 2)$....
robertdg's user avatar