In recent developments of information technologies, many new types of optimization problems appear which motivate many new research subjects in optimization theory. Especially, in viral marketing, there exist many problems whose objective functions are neither submodular nor supermodular. Those problems encourage us to extend our study from the submodular optimization to the nonsubmodular optimization. This extension requires new methodologies. In this chapter, we discuss two of them, the sandwich method and the parameterized method.