Author name cluster

Philip Lazos

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.

13 papers

2 author rows

TCS Journal 2026 Journal Article

Submodular maximization subject to a knapsack constraint: Combinatorial algorithms with near-optimal adaptive complexity

Georgios Amanatidis
Federico Fusco
Philip Lazos
Stefano Leonardi
Alberto Marchetti-Spaccamela
Rebecca Reiffenhäuser

Submodular maximization is a classic algorithmic problem with multiple applications in data mining and machine learning; there, the growing need to deal with massive instances motivates the design of algorithms balancing the quality of the solution with applicability. For the latter, an important measure is the adaptive complexity, which captures the number of sequential rounds of parallel computation needed by an algorithm to terminate. In this work, we obtain the first constant factor approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint with near-optimal O(log n) adaptive complexity. Low adaptivity by itself, however, is not enough: a crucial feature to account for is represented by the total number of function evaluations (or value queries). Our algorithm asks O ˜ ( n 2 ) value queries but can be modified to run with only O ˜ ( n ), while retaining a low adaptive complexity of O(log2 n). Besides the above improvement in adaptivity, this is also the first combinatorial approach with sublinear adaptive complexity for the problem and yields algorithms comparable to the state-of-the-art even for the special cases of cardinality constraints or monotone objectives.

Details DOI

AAMAS Conference 2025 Conference Paper

Algorithmically Fair Maximization of Multiple Submodular Objective Functions

Georgios Amanatidis
Georgios Birmpas
Philip Lazos
Stefano Leonardi
Rebecca Reiffenhäuser

Constrained maximization of submodular functions poses a central problem in combinatorial optimization. In many realistic scenarios, a number of agents need to maximize multiple submodular objectives over the same ground set. We study such a setting, where the different solutions must be disjoint, and thus, questions of algorithmic fairness arise. Inspired from the fair division literature, we suggest a simple round-robin protocol, where agents are allowed to build their solutions one item at a time by taking turns. Unlike what is typical in fair division, however, the prime goal here is to provide a fair algorithmic environment; each agent is allowed to use any algorithm for constructing their respective solutions. We show that just by following simple greedy policies, agents have solid guarantees for both monotone and non-monotone objectives, and for combinatorial constraints as general as 𝑝-systems (which capture cardinality and matroid intersection constraints). In the monotone case, our results include the first approximate EF1-type guarantees under such general constraints. Further, although following a greedy policy may not be generally optimal, we show that consistently performing better than that is computationally hard.

PDF

ECAI Conference 2025 Conference Paper

Participatory Budgeting with Donations: The Case of Selective Voters

Philip Lazos
Evangelos Markakis 0001
Georgios Papasotiropoulos

Participatory budgeting allows citizens to decide how to allocate public funds among projects. Motivated by recent real-world applications in both municipal and blockchain environments, we propose and study a framework where voters can donate additional private funds to enhance their own satisfaction, using cumulative ballots to express preferences. We introduce the first mechanisms for this setting and evaluate them primarily based on the satisfaction of axioms, while also exploring their algorithmic and strategic aspects.

Details

AAMAS Conference 2024 Conference Paper

On the Potential and Limitations of Proxy Voting: Delegation with Incomplete Votes

Georgios Amanatidis
Aris Filos-Ratsikas
Philip Lazos
Evangelos Markakis
Georgios Papasotiropoulos

We study elections where voters are faced with the challenge of expressing preferences over an extreme number of issues under consideration. This is largely motivated by emerging blockchain governance systems, which include voters with different weights and a massive number of community generated proposals. In such scenarios, it is natural to expect that voters will have incomplete preferences, as they may only be able to evaluate or be confident about a very small proportion of the alternatives. As a result, the election outcome may be significantly affected, leading to suboptimal decisions. Our central inquiry revolves around whether delegation of ballots to proxies possessing greater expertise or a more comprehensive understanding of the voters’ preferences can lead to outcomes with higher legitimacy and enhanced voters’ satisfaction in elections where voters submit incomplete preferences. To explore this, we introduce a model where potential proxies advertise their ballots over multiple issues, and each voter either delegates to a seemingly attractive proxy or casts a ballot directly. We identify necessary and sufficient conditions that could lead to a socially better outcome by leveraging the participation of proxies. We accompany our theoretical findings with experiments on instances derived from real datasets. Our results enhance the understanding of the power of delegation towards improving election outcomes.

PDF

JAIR Journal 2022 Journal Article

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint

Georgios Amanatidis
Federico Fusco
Philip Lazos
Stefano Leonardi
Rebecca Reiffenhäuser

Constrained submodular maximization problems encompass a wide variety of applications, including personalized recommendation, team formation, and revenue maximization via viral marketing. The massive instances occurring in modern-day applications can render existing algorithms prohibitively slow. Moreover, frequently those instances are also inherently stochastic. Focusing on these challenges, we revisit the classic problem of maximizing a (possibly non-monotone) submodular function subject to a knapsack constraint. We present a simple randomized greedy algorithm that achieves a 5.83-approximation and runs in O(n log n) time, i.e., at least a factor n faster than other state-of-the-art algorithms. The versatility of our approach allows us to further transfer it to a stochastic version of the problem. There, we obtain a (9 + ε)-approximation to the best adaptive policy, which is the first constant approximation for non-monotone objectives. Experimental evaluation of our algorithms showcases their improved performance on real and synthetic data.

PDF Details DOI

SODA Conference 2022 Conference Paper

Single-Sample Prophet Inequalities via Greedy-Ordered Selection

Constantine Caramanis
Paul Dütting
Matthew Faw
Federico Fusco 0001
Philip Lazos
Stefano Leonardi 0001
Orestis Papadigenopoulos
Emmanouil Pountourakis

We study single-sample prophet inequalities (SSPIs), i. e. , prophet inequalities where only a single sample from each prior distribution is available. Besides a direct, and optimal, SSPI for the basic single choice problem [Rubinstein et al. , 2020], most existing SSPI results were obtained via an elegant, but inherently lossy reduction to order-oblivious secretary (OOS) policies [Azar et al. , 2014]. Motivated by this discrepancy, we develop an intuitive and versatile greedy-based technique that yields SSPIs directly rather than through the reduction to OOSs. Our results can be seen as generalizing and unifying a number of existing results in the area of prophet and secretary problems. Our algorithms significantly improve on the competitive guarantees for a number of interesting scenarios (including general matching with edge arrivals, bipartite matching with vertex arrivals, and certain matroids), and capture new settings (such as budget additive combinatorial auctions). Complementing our algorithmic results, we also consider mechanism design variants. Finally, we analyze the power and limitations of different SSPI approaches by providing a partial converse to the reduction from SSPI to OOS given by Azar et al.

Details

STOC Conference 2021 Conference Paper

Efficient two-sided markets with limited information

Paul Dütting
Federico Fusco 0001
Philip Lazos
Stefano Leonardi 0001
Rebecca Reiffenhäuser

A celebrated impossibility result by Myerson and Satterthwaite (1983) shows that any truthful mechanism for two-sided markets that maximizes social welfare must run a deficit, resulting in a necessity to relax welfare efficiency and the use of approximation mechanisms. Such mechanisms in general make extensive use of the Bayesian priors. In this work, we investigate a question of increasing theoretical and practical importance: how much prior information is required to design mechanisms with near-optimal approximations?

Details

TCS Journal 2021 Journal Article

Reallocating multiple facilities on the line

Dimitris Fotakis
Loukas Kavouras
Panagiotis Kostopanagiotis
Philip Lazos
Stratis Skoulakis
Nikos Zarifis

We study the K-Facility Reallocation problem on the real line, where we maintain K facility locations over T stages, based on the stage-dependent locations of n agents. Each agent is connected to the nearest facility at each stage, and the facilities may move from one stage to another, to accommodate different agent locations. The objective is to minimize the connection cost of the agents plus the total moving cost of the facilities, over all stages. The K-Facility Reallocation problem was introduced by de Keijzer and Wojtczak, where they mostly focused on the special case of a single facility. Using an LP-based approach, we present a polynomial time algorithm that computes the optimal solution for any number of facilities. We also consider the online K-Facility Reallocation problem, where the algorithm becomes aware of agent locations in a stage-by-stage fashion. By exploiting an interesting connection to the classical K-server problem, we present a constant-competitive algorithm for K = 2 facilities.

Details DOI

AAMAS Conference 2021 Conference Paper

RPPLNS: Pay-per-last-N-shares with a Randomised Twist

Philip Lazos
Francisco J. Marmolejo Cossío
Xinyu Zhou
Jonathan Katz

“Pay-per-last-𝑁-shares” (PPLNS) is one of the most common payout strategies used by mining pools in Proof-of-Work (PoW) cryptocurrencies such as Bitcoin. As with any payment scheme, it is imperative to study issues of incentive compatibility of miners within the pool. For PPLNS this question has only been partially answered; we know that reasonably-sized miners within a PPLNS pool prefer following the pool protocol over employing specific deviations. In this paper, we present a novel modification to PPLNS where we randomise the protocol in a natural way. We call our protocol “Randomised pay-per-last-𝑁-shares” (RPPLNS), and note that the randomised structure of the protocol greatly simplifies the study of its incentive compatibility. We show that RPPLNS maintains the strengths of PPLNS (i. e. , fairness, variance reduction, and resistance to pool hopping), while also being robust against a richer class of strategic mining than what has been shown for PPLNS.

PDF

ICML Conference 2021 Conference Paper

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity

Georgios Amanatidis
Federico Fusco 0001
Philip Lazos
Stefano Leonardi 0001
Alberto Marchetti-Spaccamela
Rebecca Reiffenhäuser

The growing need to deal with massive instances motivates the design of algorithms balancing the quality of the solution with applicability. For the latter, an important measure is the \emph{adaptive complexity}, capturing the number of sequential rounds of parallel computation needed. In this work we obtain the first \emph{constant factor} approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint with \emph{near-optimal} $O(\log n)$ adaptive complexity. Low adaptivity by itself, however, is not enough: one needs to account for the total number of function evaluations (or value queries) as well. Our algorithm asks $\tilde{O}(n^2)$ value queries, but can be modified to run with only $\tilde{O}(n)$ instead, while retaining a low adaptive complexity of $O(\log^2n)$. Besides the above improvement in adaptivity, this is also the first \emph{combinatorial} approach with sublinear adaptive complexity for the problem and yields algorithms comparable to the state-of-the-art even for the special cases of cardinality constraints or monotone objectives. Finally, we showcase our algorithms’ applicability on real-world datasets.

Details

NeurIPS Conference 2020 Conference Paper

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint

Georgios Amanatidis
Federico Fusco
Philip Lazos
Stefano Leonardi
Rebecca Reiffenhäuser

Constrained submodular maximization problems encompass a wide variety of applications, including personalized recommendation, team formation, and revenue maximization via viral marketing. The massive instances occurring in modern-day applications can render existing algorithms prohibitively slow. Moreover, frequently those instances are also inherently stochastic. Focusing on these challenges, we revisit the classic problem of maximizing a (possibly non-monotone) submodular function subject to a knapsack constraint. We present a simple randomized greedy algorithm that achieves a $5. 83$ approximation and runs in $O(n \log n)$ time, i. e. , at least a factor $n$ faster than other state-of-the-art algorithms. The robustness of our approach allows us to further transfer it to a stochastic version of the problem. There, we obtain a 9-approximation to the best adaptive policy, which is the first constant approximation for non-monotone objectives. Experimental evaluation of our algorithms showcases their improved performance on real and synthetic data.

PDF Details

AAAI Conference 2019 Conference Paper

Multi-Unit Bilateral Trade

Matthias Gerstgrasser
Paul W. Goldberg
Bart de Keijzer
Philip Lazos
Alexander Skopalik

We characterise the set of dominant strategy incentive compatible (DSIC), strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms for the multi-unit bilateral trade setting. In such a setting there is a single buyer and a single seller who holds a finite number k of identical items. The mechanism has to decide how many units of the item are transferred from the seller to the buyer and how much money is transferred from the buyer to the seller. We consider two classes of valuation functions for the buyer and seller: Valuations that are increasing in the number of units in possession, and the more specific class of valuations that are increasing and submodular. Furthermore, we present some approximation results about the performance of certain such mechanisms, in terms of social welfare: For increasing submodular valuation functions, we show the existence of a deterministic 2-approximation mechanism and a randomised e/(1−e) approximation mechanism, matching the best known bounds for the single-item setting.

PDF Details

IJCAI Conference 2019 Conference Paper

Reallocating Multiple Facilities on the Line

Dimitris Fotakis
Loukas Kavouras
Panagiotis Kostopanagiotis
Philip Lazos
Stratis Skoulakis
Nikos Zarifis

We study the multistage K-facility reallocation problem on the real line, where we maintain K facility locations over T stages, based on the stage-dependent locations of n agents. Each agent is connected to the nearest facility at each stage, and the facilities may move from one stage to another, to accommodate different agent locations. The objective is to minimize the connection cost of the agents plus the total moving cost of the facilities, over all stages. K-facility reallocation problem was introduced by (B. D. Kaijzer and D. Wojtczak, IJCAI 2018), where they mostly focused on the special case of a single facility. Using an LP-based approach, we present a polynomial time algorithm that computes the optimal solution for any number of facilities. We also consider online K-facility reallocation, where the algorithm becomes aware of agent locations in a stage-by stage fashion. By exploiting an interesting connection to the classical K-server problem, we present a constant-competitive algorithm for K = 2 facilities.

PDF Details