MEMarianna E.-Nagy

Marianna E.-Nagy

*This is an algorithmically generated author record based on publicly available information.

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


Marianna E.-Nagy has a total of 17 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Interior-Point Algorithms for Monotone Linear Complementarity Problem Based on Different Predictor Directions

    by Marianna E.-Nagy, Tibor Illés, Yurii Nesterov, Petra Renáta Rigó

    In this paper, we introduce two parabolic target-space interior-point algorithms for solving monotone linear complementarity problems (LCPs). The first algorithm is based on a universal tangent direction, which has been recently proposed for linear optimization problems. We prove that this method has the best-known worst-case complexity bound. We extend onto this LCP its auto-correcting version proposed by Nesterov and prove its local quadratic convergence under the assumption of the existence of a unique and strictly complementarity solution. In our numerical experiments, we compare the new algorithms with a general method, recently developed for weighted monotone linear complementarity problems. Funding: This research was supported by the National Research, Development and Innovation Office (NKFIH) [Grant 2024-1.2.3-HU-RIZONT-2024-00030]. The research of M. E.-Nagy and P. R. Rigó was individually supported by the János Bolyai Research Scholarship of the Hungarian Academy of Sciences (Magyar Tudományos Akadémia) [Grants 2024-2027 and 2025-2028, respectively].

  • Comprehensive Analysis of Kernel-Based Interior-Point Methods for the \({P}_{{*}}{(\kappa )}\)-LCP

    by Zsolt Darvay, Marianna E.-Nagy, Goran Lesaja, Petra Renáta Rigó, Anita Varga

    We present an interior-point algorithm for [Formula: see text]-linear complementarity problems, based on a barrier function defined by a new class of univariate kernel functions, called standard kernel functions (SKFs). A comprehensive and unified complexity analysis of the algorithm is provided, and a general procedure is developed to determine the iteration bounds for long-step and short-step versions of the method for the entire class of SKFs. We illustrate the general procedure by determining the iteration bounds for several parametric SKFs, which include, as special cases, all eligible kernel functions from the literature that have rational or exponential barrier terms. In all cases, we match the best iteration bounds obtained in the literature for these special cases of SKFs.

  • Open Access

    Parabolic target-space interior-point algorithm for monotone weighted linear complementarity problem

    by Marianna E.-Nagy, Tibor Illés, Yurii Nesterov, Petra Renáta Rigó

    We revisit the main principles for constructing polynomial-time primal-dual interior-point algorithms (IPAs). We investigate the weighted Linear Complementarity Problem (WLCP), by extending the framework of Parabolic Target Space (PTS), proposed by Nesterov (2008) for primal-dual Linear Programming (LP) Problems. This approach has several advantages. The proposed method based on the PTS approach starts from an arbitrary strictly feasible primal-dual pair and follows a single central path toward the solution. It has the best known worst-case complexity bound. Finally, it works in a large neighborhood of the deviated central path, allowing very large steps. The latter ability results in a significant acceleration at the end of the process, confirmed by our preliminary computational experiments.


  • Open Access

    Mixed integer linear programming formulation for K-means clustering problem

    by Kolos Cs. Ágoston, Marianna E.-Nagy

    The minimum sum-of-squares clusering is the most widely used clustering method. The minimum sum-of-squares clustering is usually solved by the heuristic KMEANS algorithm, which converges to a local optimum. A lot of effort has been made to solve such kind of problems, but a mixed integer linear programming formulation (MILP) is still missing. In this paper, we formulate MILP models. The advantage of MILP formulation is that users can extend the original problem with arbitrary linear constraints. We also present numerical results, we solve these models up to sample size of 150.


  • Open Access

    Sufficient Matrices: Properties, Generating and Testing

    by Marianna E.-Nagy, Tibor Illés, Janez Povh, Anita Varga, Janez Žerovnik

    This paper investigates various aspects of sufficient matrices, one of the most relevant matrix classes introduced in connection with linear complementarity problems. We summarize the most important theoretical results and properties related to sufficient matrices. Based on these, we propose different construction rules that can be used to generate new matrices that belong to this class. A nonnegative number can be assigned to each sufficient matrix, which is called its handicap and works as a measure of sufficiency. The handicap plays a crucial role in proving convergence and complexity results for interior point algorithms for linear complementarity problems. For a particular sufficient matrix, called Csizmadia’s matrix, we give the exact value of the handicap, which is exponential in the size of the matrix. Another important topic that we address is deciding whether a matrix is sufficient. Tseng proved in 2000 that this decision problem is co-NP hard. We investigate three different algorithms for determining the sufficiency of a given matrix: Väliaho’s algorithm, a linear programming-based algorithm, and an algorithm that facilitates nonlinear programming reformulations of the definition of sufficiency. We tested the efficiency of these methods on our recently launched benchmark data set that consists of four different sets of matrices. In this paper, we give the description and most important properties of the benchmark set, which can be used in the future to compare the performance of different interior point algorithms for linear complementarity problems.


  • Open Access

    A New Ai–Zhang Type Interior Point Algorithm for Sufficient Linear Complementarity Problems

    by Marianna E.-Nagy, Anita Varga

    In this paper, we propose a new long-step interior point method for solving sufficient linear complementarity problems. The new algorithm combines two important approaches from the literature: the main ideas of the long-step interior point algorithm introduced by Ai and Zhang and the algebraic equivalent transformation technique proposed by Darvay. Similar to the method of Ai and Zhang, our algorithm also works in a wide neighborhood of the central path and has the best known iteration complexity of short-step variants. However, due to the properties of the applied transforming function in Darvay’s technique, the wide neighborhood definition in the analysis depends on the value of the handicap. We implemented not only the theoretical algorithm but a greedy variant of the new method (working in a neighborhood independent of the handicap) in MATLAB and tested its efficiency on both sufficient and non-sufficient problem instances. In addition to presenting our numerical results, we also make some interesting observations regarding the analysis of Ai–Zhang type methods.


  • Open Access

    A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation

    by Marianna E.-Nagy, Anita Varga

    In this paper, we investigate a new primal-dual long-step interior point algorithm for linear optimization. Based on the step size, interior point algorithms can be divided into two main groups, short-step, and long-step methods. In practice, long-step variants perform better, but usually, a better theoretical complexity can be achieved for the short-step methods. One of the exceptions is the large-update algorithm of Ai and Zhang. The new wide neighborhood and the main characteristics of the presented algorithm are based on their approach. In addition, we use the algebraic equivalent transformation technique of Darvay to determine new modified search directions for our method. We show that the new long-step algorithm is convergent and has the best known iteration complexity of short-step variants. We present our numerical results and compare the performance of our algorithm with two previously introduced Ai-Zhang type interior point algorithms on a set of linear programming test problems from the Netlib library.


  • Open Access

    A Comparative Research on Municipal Voluntary Tasks of Three Hungarian and Slovenian Municipalities

    by Marianna Nagy, István Hoffman, Dorottya Papp

    The article summarizes the similarities and differences in voluntary task management of municipalities. For this purpose, we carried out empirical research in three Hungarian and three Slovenian municipalities. Our main objective was to discover which economic and social factors influence the scope of voluntary tasks in Hungary and in Slovenia. We separately analysed six sectors of municipal services, with regard to the different size of the municipalities. Likewise, we only covered the major sectors in which voluntary tasks are most likely to appear and therefore can serve as a basis for comparative analysis. The analysis gradually verified the initial hypothesis of our research that voluntary tasks management is more likely to be present in cities with larger economic powers and is remarkably profounder in municipalities of touristic importance.