1. Reduction: Problem X reduces to problem Y if you can use an algorithm that solves Y to help solve X.
-- Cost of solving X = total cost of solving Y + cost of reduction.
2. Example of reduction: To solve element distinctness on N items:
-- Sort N items.
-- Check adjacent pairs for equality.
-- Cost of solving element distinctness. N log N + N .
3. Usage of Reduction : design algorithms. Since I know how to solve Y, can I use that algorithm to solve X ?
4. Convex hull reduces to sorting:
-- Choose point p with smallest (or largest) y-coordinate.
-- Sort points by polar angle with p to get simple polygon.
-- Consider points in order, and discard those that would create a clockwise turn.
-- Cost of convex hull. N log N + N.
5. Undirected shortest paths (with nonnegative weights) reduces to directed shortest path:
-- Replace each undirected edge by two directed edges.
-- Cost of undirected shortest paths. E log V + E.
-- Can still solve shortest-paths problem in undirected graphs with negative weights (if no negative cycles), but need more sophisticated techniques.(reduces to weighted non-bipartite matching)
6. Linear-time reductions involving familiar problems:
7. Reduction usage: establishing lower bounds. If I could easily solve Y, then I could easily solve X. If I can’t easily solve X. Therefore, I can’t easily solve Y.
8. Linear-time reductions: Problem X linear-time reduces to problem Y if X can be solved with:
-- Linear number of standard computational steps.
-- Constant number of calls to Y.
9. Sorting linear-time reduces to convex hull.
-- Sorting instance: x1, x2, ... , xN.
-- Convex hull instance: (x1 , x1^2 ), (x2, x2^2 ), ... , (xN , xN^2 ).
-- Region { x : x^2 ≥ x } is convex ⇒ all points are on hull.
-- Starting at point with most negative x, counterclockwise order of hull points yields integers in ascending order.
10. Establishing lower bounds through reduction is an important tool in guiding algorithm design efforts.
11. Reduction usage: Classifying problems. Prove that two problems X and Y have the same complexity
-- show that problem X linear-time reduces to Y.
-- show that Y linear-time reduces to X.
-- Conclude that X and Y have the same complexity. ( even if we don't know what the complexity is!)
12. A possible real-world scenario.
-- System designer specs the APIs for project.
-- Alice implements sort() using convexHull().
-- Bob implements convexHull() using sort().
-- Infinite reduction loop!
13. Integer arithmetic problems with the same complexity as integer multiplication
14. Numerical linear algebra problems with the same complexity as matrix multiplication
15. Summary:
-- Reductions are important in theory to:
- Design algorithms.
- Establish lower bounds.
- Classify problems according to their computational requirements.
-- Reductions are important in practice to:
- Design algorithms.
- Design reusable software modules.
- Determine difficulty of your problem and choose the right tool.
相关推荐
reduction. We divide the methods into projective methods and methods that model the manifold on which the data lies. For projective methods, we review projection pursuit, principal component analysis ...
This Book discusses machine learning for model order reduction, which can be used in modern VLSI design to predict the behavior of an electronic circuit, via mathematical models that predict behavior....
This Book discusses machine learning for model order reduction, which can be used in modern VLSI design to predict the behavior of an electronic circuit, via mathematical models that predict behavior....
Data Reduction and Error Analysis for the physical sciences- Bevington, Philip R
Multi-Label dimensionality Reduction Multi-label learning concerns supervised learning problems in which each instance may be associated with multiple labels simultaneously. A key difference between ...
Advanced Noise Reduction for Mobile Telephony
Compression Artifacts Reduction by a Deep Convolutional Network
Power Supply Noise Reduction
The text provides a lucid summary of facts and concepts relating to well-known methods as well as recent developments in nonlinear dimensionality reduction. Methods are all described from a unifying ...
Machine Learning for Model Order Reduction 英文epub 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国亚马逊官网搜索此书
Peak_Cancellation_Crest_Factor_Reduction_Reference_Design xlinx的PC-CFR设计详细说明,教你如何用matlab搭建PC-CFR,可以用搭建的PC-CFR生产设计代码
Variance reduction techniques and quasi-Monte Carlo methods ☆
Kalman Filter for Noise Reduction and Dynamical Tracking
论文《Dimensionality Reduction-A Comparative Review》自制课堂用交流ppt,上传以方便同样阅读此论文的朋友阅读理解,全文已译,学习交流考虑所以设置0积分下载,请勿二传。
A survey of dimensionality reduction techniques - 机器学习之降维实现
Optimizing parallel reduction in CUDA 规约优化文档
该文档为HPE 3PAR Adaptive Data Reduction技术说明,全英文。
Information Technology in Disaster Risk Reduction,Second IFIP TC 5 DCITDRR International Conference, ITDRR 2017, Sofia, Bulgaria, October 25-27, 2017, Revised Selected Papers
文献阅读报告White-Box Transformers via Sparse Rate Reduction.docx
A noise reduction processor for Mobile voice communication.