Skip to main content

All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
64 views

Alternatives to McCormick Envelope

I have an optimization problem for which I have the optimal solution obtained by the ILP. However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
LyLa's user avatar
  • 3
0 votes
0 answers
96 views

Why is Gaussian distribution always chosen for smoothed analysis?

I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...
mc.math's user avatar
  • 29
0 votes
1 answer
76 views

A question on graph partitioning

Given a connected un-directed simple graph $G=(V,E)$, is there a polynomial time algorithm to find the smallest subset $S$ of $V$ such that each node in $V \setminus S$ has at least 50% of its ...
DSM's user avatar
  • 1,216
0 votes
1 answer
61 views

Variant of the linear programming problem

Good afternoon, my experience in mathematical programming is low. I would like to know if there is any general method to address the following problem: $$\text{Minimize }\sum_{i=1}^n d_i(x_j)$$ $$s.a....
Rusbert's user avatar
  • 193
4 votes
0 answers
539 views

Using Linear Programming as an iterative procedure

Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
D. Rusin's user avatar
  • 391
0 votes
1 answer
212 views

Is an exact violated inequality constraint met as equal constraint in optimal solution?

We have a solution which does not satisfied exactly one inequality constraint in linear program. The corresponding dual solution is also feasible. Is it correct this constraint is in equal form in the ...
A.R.S's user avatar
  • 25
0 votes
0 answers
21 views

Easy instance of set cover

I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
Tom Solberg's user avatar
  • 4,049