New approximations for monotone submodular maximization with knapsack constraint

Abstract Given a monotone submodular set function with a knapsack constraint, its maximization problem has two types of approximation algorithms with running time $$O(n^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and $$O(n^5)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>5</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , respectively. With running time $$O(n^5)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>5</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , the best performance ratio is $$1-1/e$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>e</mml:mi> </mml:mrow> </mml:math> . With running time $$O(n^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , the well-known performance ratio is $$(1-1/e)/2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>e</mml:mi> <mml:mo>)</mml:mo> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> and an improved one is claimed to be $$(1-1/e^2)/2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:msup> <mml:mi>e</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> recently. In this paper, we design an algorithm with running $$O(n^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and performance ratio $$1-1/e^{2/3}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:msup> <mml:mi>e</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> , and an algorithm with running time $$O(n^3)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and performance ratio 1/2.