TAILIEUCHUNG - Đề tài " On the hardness of approximating minimum vertex cover "

We prove the Minimum Vertex Cover problem to be NP-hard to approximate to within a factor of , extending on previous PCP and hardness of approximation technique. To that end, one needs to develop a new proof framework, and to borrow and extend ideas from several fields. 1. Introduction The basic purpose of computational complexity theory is to classify computational problems according to the amount of resources required to solve them. In particular, the most basic task is to classify computational problems to those that are efficiently solvable and those that are not. . | Annals of Mathematics On the hardness of approximating minimum vertex cover By Irit Dinur and Samuel Safra Annals of Mathematics 162 2005 439 485 On the hardness of approximating minimum vertex cover By Irit Dinur and Samuel Safra Abstract We prove the Minimum Vertex Cover problem to be NP-hard to approximate to within a factor of extending on previous PCP and hardness of approximation technique. To that end one needs to develop a new proof framework and to borrow and extend ideas from several fields. 1. Introduction The basic purpose of computational complexity theory is to classify computational problems according to the amount of resources required to solve them. In particular the most basic task is to classify computational problems to those that are efficiently solvable and those that are not. The complexity class P consists of all problems that can be solved in polynomial-time. It is considered for this rough classification as the class of efficiently solvable problems. While many computational problems are known to be in P many others are neither known to be in P nor proven to be outside P. Indeed many such problems are known to be in the class NP namely the class of all problems whose solutions can be verified in polynomial-time. When it comes to proving that a problem is outside a certain complexity class current techniques are radically inadequate. The most fundamental open question of complexity theory namely the P vs. NP question may be a particular instance of this shortcoming. While the P vs. NP question is wide open one may still classify computational problems into those in P and those that are NP-hard Coo71 Lev73 Kar72 . A computational problem L is NP-hard if its complexity epitomizes the hardness of NP. That is any NP problem can be efficiently reduced to L. Thus the existence of a polynomial-time solution for L implies P NP. Consequently showing P NP would immediately rule out an efficient algorithm Research supported in part by the Fund

• Thạc sĩ - Tiến sĩ - Cao học
• hardness
• approximating
• subjects of mathematics
• science reports
• studied mathematics
• natural sciences
• scientific research
• Effects of workpiece hardness
• Hard turned surfaces of alloy steels
• 9XC and X12M alloy steels
• The workpiece’s hardness of HRC
• Machined surface roughness
• Variable work piece hardness on surface roughness
• End milling using multiple regression
• Adaptive Neuro fuzzy inference systema
• CNC end milling operation
• Work piece of different hardness
• Viterbi Training for PCFGs
• Hardness Results and Competitiveness
• Uniform Initialization
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• Electrical discharge machining
• Alloy steel hardness
• Material removal rate
• Workpiece surface roughness
• Taguchi methodology
• Linear regression model
• Rockwell hardness
• Tensile strength
• Stainless steel heat treatment
• PWR pressure water reactor
• Nuclear power plants
• Rockwell hardness tester
• Physical and bacteriological quality
• MPN count
• Jabalpur city
• Most probable number
• pH and total hardness of water sources
• Bacteriological quality of water based
• Multi response optimization
• Powder mixed electrical discharge machining
• Surface micro hardness
• Pulse on time
• Pulse off time
• Particle contents
• Stir casting process
• Hardness in Al (Si Mg) cast composites
• Fly ash particle reinforcement
• Turning burnishing operation
• Vickers hardness
• Aluminum 6061
• Improving roughness
• Compressed air assisted turning burnishing process
• Coconut oil of mixtures of cocoa powder
• Milk powder on the viscosity
• Hardness of mixtures of cocoa powder and cocoa butter
• Cocoa powder/cocoa butter
• Replacement of cocoa powder
• Experimental investigation of impact hybrid laminated plates
• Hardness properties of hybrid laminated plates
• Hybrid laminated plates
• Mixing Silicon Carbide
• Internal burnishing
• Surface roughness
• Minimum quantity lubrication
• Burnishing operations
• kinh doanh
• quản trị kinh doanh
• quản trị doanh nghiệp
• doanh nghiệp
• quản trị nhân sự
• cách cư xử
• cách quản lý
• tài liệu kỹ thuật
• tài liệu công nghệ
• tài liệu viễn thông
• chuyên ngành viễn thông
• giáo trình viễn thông
• Thiết kế máy
• cơ khí chế tạo
• cấp phôi tự động
• máy nâng chuyển
• máy kéo
• v
• Watercolor
• Drawing Technique
• drawing pencil
• Art Tutorial
• Pencil portrait
• Pet Portrait
• drawing portrait
• stars portrait
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• công trình toán học
• Báo cáo lâm nghiệp hay
• báo cáo lâm nghiệp
• công trình nghiên cứu lâm nghiệp
• tài liệu về lâm nghiệp
• Material requirements
• General requirements
• Absorbed energy
• Hardness variation
• Process control
• Grain size
• Bleaching on the wood
• Bleaching methods
• Sodium hydroxide
• Hydrogen peroxide
• Calcium peroxide
• Hydrochloric acid and varnish
• Journal of Science and Technology
• The effect of diane epoxy resin
• Poly divinyl ether
• Diane epoxy resin
• Relative hardness and gel fraction
• Vietnam Journal of Science and Technology
• Aluminum phosphate sealant containing Al2O3 nanoparticles
• The Al2O3 TiO2 plasma sprayed coating
• Aluminum phosphate uncontain Al2O3 nanoparticles
• The unsealed coating
• The Polyurea coatings
• Provide high hardness
• Polyaspartic acid esters
• The weather resistance
• Polyisocyanate curing agent
• Thickness determination and control
• Functional Ni–composite electrodeposited coatings
• High hardness Ni–CBN
• Tightly adherent and evenly dispersed