In:
International Journal of Foundations of Computer Science, World Scientific Pub Co Pte Ltd
Abstract:
In this paper, we propose a concept of a lattice pseudo-submodular (LPS) function and consider maximizing a monotone continuous real LPS function [Formula: see text] under a convex polytope constraint. The concept of LPS function was proposed to describe the properties of some discrete functions or nonconvex continuous functions. It is a generalization of the lattice submodular function. For the real LPS maximization problem, we design the monotone Pseudo Frank-Wolfe (PFW) algorithm by taking advantage of the second derivative bound. The PFW algorithm iterates by constantly optimize linear gradient function [Formula: see text] , and finally outputs the solution. We theoretically prove that PFK algorithm has an approximation ratio of [Formula: see text] (where [Formula: see text] ), and it needs at least [Formula: see text] rounds (where [Formula: see text] is a parameter given in advance). The PFW algorithm is also useful for multilinear extension of discrete lattice pseudo-submodular maximization problems.
Type of Medium:
Online Resource
ISSN:
0129-0541
,
1793-6373
DOI:
10.1142/S0129054122460091
Language:
English
Publisher:
World Scientific Pub Co Pte Ltd
Publication Date:
2023
Permalink
