All Questions

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

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

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

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