Bilkent University
Department of Computer Engineering

---

S E M I N A R

 

Combinatorial Reductions for Parallel and Scientific Computing: 2 Examples

 

Enver Kayaaslan
MSc.Student
Computer Engineering Department
Bilkent University

Combinatorics is used as a powerful tool to solve some important problems emerging in parallel and scientific computing. Scientific computing deals with the problems that come out at different fields of science, such as solving partial differential equations for propogation of electrodynamics in physics. Parallel computing is used to provide faster solutions to problems due to the parallelism. On the other hand, combinatorics is a branch of pure mathematics studying on discrete objects and deals with combinatorial problems such as Minimum Vertex Cover and Graph/Hypergraph Partitioing. Combinatorial algorithms (solutions to combinatorial problems) is a well-studied area in computer science. Therefore, reducing problems (arising in parallel and scientific computing) into combinatorial problems will be a smart way to deal with these problems.In this presentation, there will be given two examples of combinatorial reduction. One problem comes out from scientific computing whereas the other is a problem arising at parallel computing. The scientific computing problem that will be presented is reducing constraints of a Linear Programming matrix A in such a way that A^T D A will remain same topologically. This problem is showed to be NP-complete and reduced to Minimum Set Cover problem. The parallel computing problem that will be presented is non-preemptive load balancing of tasks to homogeneous processors where for each task at most two processors are eligible to process. This problem is reduced to Maximum Flow problem.

 

DATE: 13 April, 2009, Monday@ 16:20
PLACE: EA 409