Refine your search
Collections
Co-Authors
Year
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z All
Maaroju, Narendhar
- Approximation Algorithms for NP-Problems
Abstract Views :195 |
PDF Views:2
Authors
Affiliations
1 Thapar University, Patiala, IN
1 Thapar University, Patiala, IN
Source
Automation and Autonomous Systems, Vol 1, No 2 (2009), Pagination: 35-41Abstract
Algorithms are at the heart of problem solving in scientific computing and computer science. Unfortunately many of the combinatorial problems that arise in a computational context are NP-hard, so that optimal solutions are unlikely to be found in polynomial time. How can we cope with this intractability? One approach is to design algorithms that find approximate solutions guaranteed to be within some factor of the quality of the optimal solution. More recently, in large-scale scientific computing, even polynomial time algorithms that find exact solutions are deemed too expensive to be practical, and one needs faster (nearly linear time) approximation algorithms. We will consider the design of approximation algorithms for various graph-theoretical and combinatorial problems that commonly arise in scientific computing and computational biology. These include set covers (vertex covers in hypergraphs), matching, coloring, and multiple sequence alignments in computational biology.Keywords
Approximation, Optimization, MCMC, Online Computation, Randomization.- Complete Algorithms on Minimum Vertex-Cover
Abstract Views :187 |
PDF Views:2
Authors
Affiliations
1 Thapar University, Patiala, IN
1 Thapar University, Patiala, IN