Name
Abstract | ||
|---|---|---|
We consider new parameterizations of NP-optimization problems that have nontrivial lower and/or upper bounds on their optimum solution size. The natural parameter, we argue, is the quantity above the lower bound or below the upper bound. We show that for every problem in MAX SNP, the optimum value is bounded below by an unbounded function of the input-size, and that the above-guarantee parameterization with respect to this lower bound is fixed-parameter tractable. We also observe that approximation algorithms give nontrivial lower or upper bounds on the solution size and that the above or below guarantee question with respect to these bounds is fixed-parameter tractable for a subclass of NP-optimization problems. We then introduce the notion of 'tight' lower and upper bounds and exhibit a number of problems for which the above-guarantee and below-guarantee parameterizations with respect to a tight bound is fixed-parameter tractable or W-hard. We show that if we parameterize ''sufficiently'' above or below the tight bounds, then these parameterized versions are not fixed-parameter tractable unless P=NP, for a subclass of NP-optimization problems. We also list several directions to explore in this paradigm. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.jcss.2008.08.004 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
np -optimization problems,fixed-parameter tractable,above guarantee parameterizations,tight bound,above-guarantee parameterization,optimum solution size,np-optimization problem,fixed-parameter tractability,upper bound,below-guarantee parameterizations,new parameterizations,parameterized complexity,solution size,optimum value,optimization problem,lower bound,np | Approximation algorithm,Discrete mathematics,Parameterized complexity,Combinatorics,Parametrization,Np optimization problems,Upper and lower bounds,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
75 | 2 | Journal of Computer and System Sciences |
Citations | PageRank | References |
53 | 1.97 | 31 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| Venkatesh Raman | 2 | 2268 | 153.49 |
| Somnath Sikdar | 3 | 420 | 25.31 |