Arrow Research search

Author name cluster

Francesco Cellinese

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
2 author rows

Possible papers

2

I&C Journal 2021 Journal Article

Generalized budgeted submodular set function maximization

  • Francesco Cellinese
  • Gianlorenzo D'Angelo
  • Gianpiero Monaco
  • Yllka Velaj

In the generalized budgeted submodular set function maximization problem, we are given a ground set of elements and a set of bins. Each bin has its own cost and the cost of each element depends on its associated bin. The goal is to find a subset of elements along with an associated set of bins such that the overall costs of both is at most a given budget, and the profit is maximized. We present an algorithm that guarantees a 1 2 ( 1 − 1 e α ) -approximation, where α ≤ 1 is the approximation factor of an algorithm for a sub-problem. If the costs satisfy a specific condition, we provide a polynomial-time algorithm that gives us α = 1 − ϵ, while for the general case we design an algorithm with α = 1 − 1 e − ϵ. We extend our results providing a bi-criterion approximation algorithm where we can spend an extra budget up to a factor β ≥ 1 to guarantee a 1 2 ( 1 − 1 e α β ) -approximation.

Details DOI

MFCS Conference 2018 Conference Paper

Generalized Budgeted Submodular Set Function Maximization

  • Francesco Cellinese
  • Gianlorenzo D'Angelo
  • Gianpiero Monaco
  • Yllka Velaj

In this paper we consider a generalization of the well-known budgeted maximum coverage problem. We are given a ground set of elements and a set of bins. The goal is to find a subset of elements along with an associated set of bins, such that the overall cost is at most a given budget, and the profit is maximized. Each bin has its own cost and the cost of each element depends on its associated bin. The profit is measured by a monotone submodular function over the elements. We first present an algorithm that guarantees an approximation factor of 1/2(1-1/e^alpha), where alpha <= 1 is the approximation factor of an algorithm for a sub-problem. We give two polynomial-time algorithms to solve this sub-problem. The first one gives us alpha=1- epsilon if the costs satisfies a specific condition, which is fulfilled in several relevant cases, including the unitary costs case and the problem of maximizing a monotone submodular function under a knapsack constraint. The second one guarantees alpha=1-1/e-epsilon for the general case. The gap between our approximation guarantees and the known inapproximability bounds is 1/2. We extend our algorithm to a bi-criterion approximation algorithm in which we are allowed to spend an extra budget up to a factor beta >= 1 to guarantee a 1/2(1-1/e^(alpha beta))-approximation. If we set beta=1/(alpha)ln (1/(2 epsilon)), the algorithm achieves an approximation factor of 1/2-epsilon, for any arbitrarily small epsilon>0.

Details
v2026.09.13