Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Sparsification and subexponential approximation
Bonnet E., Paschos V. Acta Informatica55 (1):1-15,2018.Type:Article
Date Reviewed: Jun 14 2018

A sparsification of a problem maps the problem to a set of similar problems, each of which has its parameters bounded by some fixed number. For example, in the case of a graph-based problem, the degree might be one parameter. The solutions of these sparser problems should then map to a solution of the original problem.

The authors illustrate the notion of sparsification using MIN VERTEX COVER as an example. The paper’s main idea is to refine the notion of a sparsification to require that the solutions to the set of problems give rise to a solution to the original problem that approximates the optimal value for a solution to the original problem. Typically the problems studied are MIN DOMINATING SET, MIN FEEDBACK VERTEX SET, MIN SET COVER, and MIN FEEDBACK ARC SET, among others. This paper uses the notion of an approximation preserving sparsification, defined in detail by the authors, to show that, assuming the exponential time hypothesis (ETH), the problems listed above cannot be approximately solved to within a specified approximation by algorithms having explicitly given exponential time constraints determined by the ETH.

The paper contains detailed proofs of the results, and a useful appendix includes definitions of all the problems discussed. The paper will be of interest to people interested in the question of computing optimal solutions to any of the problems referred to here.

Reviewer:  J. P. E. Hodgson Review #: CR146082 (1808-0438)
Bookmark and Share
  Featured Reviewer  
 
Approximation (G.1.2 )
 
 
Optimization (B.1.4 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Approximation": Date
Computing surfaces of constant mean curvature with singularities
Hewgill D. Computing 32(1): 81-92, 1984. Type: Article
Mar 1 1985
A method for the calculation of eigenfunction expansions
Michell J., Drake J., Bracho S. Mathematics and Computers in Simulation XXVI(5): 443-447, 1984. Type: Article
May 1 1985
Calculation of special functions: the gamma function, the exponential integrals and error-like functions
van der Laan C., Temme N., Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands, 1984. Type: Book (9789789061962779)
Jan 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy