Alexander Grosz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Alexander Grosz has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Yiannis Giannakopoulos
School of Computing Science, University of Glasgow, Glasgow, United Kingdom
2 shared publications - Harald Hofstätter
Reitschachersiedlung 4/6 7100 Neusiedl am See Austria
1 shared publication - Othmar Koch
University of Vienna
1 shared publication - Themistoklis Melissourgos
University of Essex, Colchester, United Kingdom
1 shared publication - Themistoklis Melissourgos
University of Essex
1 shared publication - Winfried Auzinger
TU Wien
1 shared publication
Latest Publications
- 22 September 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
On the Smoothed Complexity of Combinatorial Local Search
We propose a unifying framework for smoothed analysis of combinatorial local optimization problems and show how a variety of problems within the complexity class PLS (Polynomial Local Search) can be cast within this model. This abstraction enables identifying key structural properties, and corresponding parameters, that determine the smoothed running time of local search dynamics. Our black-box tool provides concrete bounds on the expected maximum number of steps needed until local search reaches an exact local optimum. We demonstrate its power by instantiating it for various PLS-hard problems of interest to derive efficient smoothed running times. Most notably, we introduce smoothed analysis models for finding pure Nash equilibria in congestion games and network congestion games under various representations of resource latency functions. We show that even for PLS-hard instances, better-response dynamics terminate in polynomial smoothed time. Further applications include local maximum-cut on weighted graphs, the travelling salesman problem under the k-Opt heuristic, and network coordination games. Funding: A. Grosz was supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (Bundesministerium für Bildung und Forschung).
- 22 September 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
On the Smoothed Complexity of Combinatorial Local Search
We propose a unifying framework for smoothed analysis of combinatorial local optimization problems and show how a variety of problems within the complexity class PLS (Polynomial Local Search) can be cast within this model. This abstraction enables identifying key structural properties, and corresponding parameters, that determine the smoothed running time of local search dynamics. Our black-box tool provides concrete bounds on the expected maximum number of steps needed until local search reaches an exact local optimum. We demonstrate its power by instantiating it for various PLS-hard problems of interest to derive efficient smoothed running times. Most notably, we introduce smoothed analysis models for finding pure Nash equilibria in congestion games and network congestion games under various representations of resource latency functions. We show that even for PLS-hard instances, better-response dynamics terminate in polynomial smoothed time. Further applications include local maximum-cut on weighted graphs, the travelling salesman problem under the k-Opt heuristic, and network coordination games. Funding: A. Grosz was supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (Bundesministerium für Bildung und Forschung).
- Open Access
On the Smoothed Complexity of Combinatorial Local Search
We propose a unifying framework for smoothed analysis of combinatorial local optimization problems and show how a diverse selection of problems within the complexity class PLS can be cast within this model. This abstraction allows us to identify key structural properties, and corresponding parameters, that determine the smoothed running time of local search dynamics. We formalize this via a black-box tool that provides concrete bounds on the expected maximum number of steps needed until local search reaches an exact local optimum. This bound is particularly strong, in the sense that it holds for any starting feasible solution, any choice of pivoting rule, and does not rely on the choice of specific noise distributions that are applied on the input, but it is parameterized by just a global upper bound $\phi$ on the probability density. We then demonstrate the power of this tool by instantiating it for various PLS-hard problems to derive efficient smoothed running times. This not only unifies, and greatly simplifies, prior existing positive results, but also allows us to extend or improve them. Notable problems on which we provide such a contribution are Max-Cut, the Travelling Salesman problem, and Network Coordination Games. Additionally, in this paper we propose novel smoothed analysis formulations, and prove polynomial smoothed running times, for important local optimization problems that have not been studied before from this perspective. Importantly, we provide an extensive study of the problem of finding pure Nash equilibria in general and Network Congestion Games under various representation models, including explicit, step-function, and polynomial latencies. We show that all the problems we study can be solved by their standard local search algorithms in polynomial smoothed time on PLS-hard instances in which these algorithms have exponential worst-case running time.Open AccessOn the Smoothed Complexity of Combinatorial Local Search
We propose a unifying framework for smoothed analysis of combinatorial local optimization problems and show how a diverse selection of problems within the complexity class PLS can be cast within this model. This abstraction allows us to identify key structural properties, and corresponding parameters, that determine the smoothed running time of local search dynamics. We formalize this via a black-box tool that provides concrete bounds on the expected maximum number of steps needed until local search reaches an exact local optimum. This bound is particularly strong, in the sense that it holds for any starting feasible solution, any choice of pivoting rule, and does not rely on the choice of specific noise distributions that are applied on the input, but it is parameterized by just a global upper bound $\phi$ on the probability density. We then demonstrate the power of this tool by instantiating it for various PLS-hard problems to derive efficient smoothed running times. This not only unifies, and greatly simplifies, prior existing positive results, but also allows us to extend or improve them. Notable problems on which we provide such a contribution are Max-Cut, the Travelling Salesman problem, and Network Coordination Games. Additionally, in this paper we propose novel smoothed analysis formulations, and prove polynomial smoothed running times, for important local optimization problems that have not been studied before from this perspective. Importantly, we provide an extensive study of the problem of finding pure Nash equilibria in general and Network Congestion Games under various representation models, including explicit, step-function, and polynomial latencies. We show that all the problems we study can be solved by their standard local search algorithms in polynomial smoothed time on PLS-hard instances in which these algorithms have exponential worst-case running time.