Irit Katriel

TCS Journal 2008 Journal Article

Commitment under uncertainty: Two-stage stochastic matching problems

• Irit Katriel
• Claire Kenyon-Mathieu
• Eli Upfal

We define and study two versions of the bipartite matching problem in the framework of two-stage stochastic optimization with recourse. In one version, the uncertainty is in the second stage costs of the edges, and in the other version, the uncertainty is in the set of vertices that needs to be matched. We prove lower bounds, and analyze efficient strategies for both cases. These problems model real-life stochastic integral planning problems, such as commodity trading, reservation systems and scheduling under uncertainty.

MFCS Conference 2007 Conference Paper

Dynamic Matchings in Convex Bipartite Graphs

• Gerth Stølting Brodal
• Loukas Georgiadis
• Kristoffer Arnsfelt Hansen
• Irit Katriel

Abstract We consider the problem of maintaining a maximum matching in a convex bipartite graph G = ( V, E ) under a set of update operations which includes insertions and deletions of vertices and edges. It is not hard to show that it is impossible to maintain an explicit representation of a maximum matching in sub-linear time per operation, even in the amortized sense. Despite this difficulty, we develop a data structure which maintains the set of vertices that participate in a maximum matching in O (log 2 | V |) amortized time per update and reports the status of a vertex (matched or unmatched) in constant worst-case time. Our structure can report the mate of a matched vertex in the maximum matching in worst-case O ( min { k log 2 | V | + log| V |, | V | log| V |}) time, where k is the number of update operations since the last query for the same pair of vertices was made. In addition, we give an \(O(\sqrt{|V|} \log^2{|V|})\) -time amortized bound for this pair query.

AAAI Conference 2007 Conference Paper

Propagating Knapsack Constraints in Sublinear Time

• Irit Katriel
• Eli Upfal

We develop an efficient incremental version of an existing cost-based filtering algorithm for the knapsack constraint. On a universe of n elements, m invocations of the algorithm require a total of O(n log n+mk log(n/k)) time, where k ≤ n depends on the specific knapsack instance. We show that the expected value of k is significantly smaller than n on several interesting input distributions, hence while keeping the same worst-case complexity, on expectation the new algorithm is faster than the previously best method which runs in amortized linear time. After a theoretical study, we introduce heuristic enhancements and demonstrate the new algorithm’s performance experimentally.

SODA Conference 2005 Conference Paper

Online topological ordering

• Irit Katriel
• Hans L. Bodlaender