Events by date

Title: A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints, Part II

Abstract: We consider the bilevel knapsack problem with interdiction constraints, a generalization of 0-1 knapsack. In this problem, there are two knapsacks and n items. The objective is to select some items to pack into the first knapsack (i.e. interdict) such that the maximum profit attainable from packing the remaining items into the second knapsack is minimized.

Title: An Approximate Generalization of the Okamura-Seymour Theorem

Abstract: We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands.