Engineering of Approximation Algorithms for Matching and Covering in Hypergraphs and Large Graphs

Description

 

Prof. Dr. rer. nat. Anand Srivastav; Christian-Albrechts-Universität Kiel

 

Project website

 

Matching in Hypergraphs

 

In the b-matching problem, we aim to select as many edges from a hypergraph as possible while allowing only b of them to overlap in each vertex. This problem and related ones have many applications in medicine, computational geometry, and combinatorial auctions. The b-matching problem is NP-hard even if restricting to simple-structured instances. For large b, constant-factor approximations are achieved by randomized rounding. However, applications often demand small b. For small b, oblivious greedy algorithms are state-of-the-art on the theoretical side; those incorporate graph parameters such as the number of vertices in the approximation guarantee.

A goal of our project is the development of non-oblivious algorithms that work well for small b, and better than the oblivious ones. We consider combinatorial and LP-based techniques, separately as well as in combination. At the same time, we improve the known inapproximability theory.

 

Matching in Large Graphs

 

With graphs containing a large number of edges, the random access model has to be reconsidered, since random access can result in excessive seek times. The new approach is to treat a graph as a stream of edges. Algorithms now cannot simply determine, e.g., whether two vertices are adjacent or not. Instead, algorithms have to make use of edges as they go by in the stream. They may pass over the stream multiple times, but the number of passes should be strictly limited.

In our project we design streaming algorithms for matching in bipartite and general graphs. In the first phase, we presented an approximation scheme for the bipartite case and proved a worst-case bound on the number of passes depending only polynomially on the approximation parameter. Ongoing research is concerned with experimentally analyzing and improving this algorithm. Moreover, the extension to general graphs is investigated.

  
  

Publications

  • S. Eggert, L. Kliemann, P. Munstermann and A. Srivastav. "Bipartite Matching in the Semi-Streaming Model", Algorithmica, Vol. 63. 2011, pp. 490-508. [More] 
  • M. El Ouali, A. Fretwurst and A. Srivastav. "Inapproximability of $b$-Matching in $k$-uniform Hypergraphs". Proceedings of the 5th International Workshop on Algorithms and Computation, New Delhi, India, February 2011 (WALCOM 2011). 2011. pp. 57-69. [More] 
  • L. Kliemann. "Matching in Bipartite Graph Streams in a Small Number of Passes (Extended Abstract)". Proceedings of the 10th International Symposium on Experimental and Efficient Algorithms, Kolimpari, Chania, Crete, Greece, May 2011 (SEA 2011). 2011. pp. 254-266. [More] 
  • J. Rückelt, V. Sauerland, T. Slawig, A. Srivastav, B. A. Ward and C. Patvardhan. "Parameter Optimization and Uncertainty Analysis in a Model of Oceanic CO2 Uptake Using a Hybrid Algorithm and Algorithmic Differentiation", Nonlinear Analysis: Real World Applications, Vol. 11. 2010, pp. 3993-4009. [More] 
  • C. Patvardhan, P. Prakash and A. Srivastav. "A Novel Quantum-inspired Evolutionary Algorithm for the Quadratic Knapsack Problem". Proceedings of the International Conference on Operations Research Applications In Engineering And Management, Tiruchirappalli, India, May 2009 (ICOREM 2009). 2009. pp. 2061-2064. [More] 
View All
[ Back ]