### Slobodan Jelić

School of Applied Mathematics and Informatics

Josip Juraj Strossmayer University of Osijek

Josip Juraj Strossmayer University of Osijek

### Research Interests

- Combinatorial optimization
- Approximation Algorithms
- Linear optimization
- Massively parallel computing

### Degrees

**dr. sc.**, University of Zagreb, PMF – Department of Mathematics, Croatian Doctoral Study of Mathematics, Zagreb, 2015.- PhD thesis: Fast approximation algorithms for connected set cover problem and related problems (in Croatian)

**mag. math.**, University of J. J. Strossmayer, Department of mathematics, Graduate Study of Mathematics, branch: Financial and Business Mathematics, Osijek, 2009.- master thesis: Approximation Algorithms for Optimal Stage Illumination (in Croatian)

**univ. bacc. math.**, University of J. J. Strossmayer, Department of mathematics, Undergraduate Study of Mathematics, Osijek, 2007.- bachelor thesis: Gaussian Method for Solving of Systems of Linear Equations (in Croatian)

### Publications

Journal Publications

- S. Canzar, V. Hoan Do, S. Jelić, S. Laue, D. Matijević, T. Prusina, Metric multidimensional scaling for large single-cell datasets using neural networks, Algorithms for Molecular Biology
**19**/21 (2024)Metric multidimensional scaling is one of the classical methods for embedding data into low-dimensional Euclidean space. It creates the low-dimensional embedding by approximately preserving the pairwise distances between the input points. However, current state-of-the-art approaches only scale to a few thousand data points. For larger data sets such as those occurring in single-cell RNA sequencing experiments, the running time becomes prohibitively large and thus alternative methods such as PCA are widely used instead. Here, we propose a simple neural network-based approach for solving the metric multidimensional scaling problem that is orders of magnitude faster than previous state-of-the-art approaches, and hence scales to data sets with up to a few million cells. At the same time, it provides a non-linear mapping between high- and low-dimensional space that can place previously unseen cells in the same embedding. - S. Jelić, D. Ševerdija, Government Formation Problem, Central European Journal of Operations Research (2017), prihvaćen za objavljivanjeIn addition to the same political and ideological attitudes, members of political parties can be interconnected at private and/or professional levels. They are considered as a part of one large social network. After democratic elections, the total effectiveness and stability of a government may depend on expertness and cooperability of its members. Our main goal is not to give a mechanism for pre-elective government formation, but to propose a model that decides what can be a good subset of candidates for positions in the new government. The decision is based on expertness of candidates and their interconnections in the social network. Inspired by the team formation problem in a social network, we present a Government Formation Problem (GFP). We prove that this problem is NP-hard and give an algorithm based on integer linear programming formulation. In the experimental part, we test our algorithm on simulated data using the GUROBI MILP solver.
- S. Jelić, S. Laue, D. Matijević, P. Wijerama, A Fast Parallel Implementation of a PTAS for Fractional Packing and Covering Linear Programs, International Journal of Parallel Programming
**43**/5 (2015), 840-875We present a parallel implementation of the randomized (1+ε) approximation algorithm for packing and covering linear programs presented by Koufogiannakis and Young (2007). Their approach builds on ideas of the sublinear time algorithm of Grigoriadis and Khachiyan’s (Oper Res Lett 18(2):53–58, 1995) and Garg and Könemann’s (SIAM J Comput 37(2):630–652, 2007) non-uniform-increment amortization scheme. With high probability it computes a feasible primal and dual solution whose costs are within a factor of 1+ε of the optimal cost. In order to make their algorithm more parallelizable we also implemented a deterministic version of the algorithm, i.e. instead of updating a single random entry at each iteration we updated deterministically many entries at once. This slowed down a single iteration of the algorithm but allowed for larger step-sizes which lead to fewer iterations. We use NVIDIA’s parallel computing architecture CUDA for the parallel environment. We report a speedup between one and two orders of magnitude over the times reported by Koufogiannakis and Young (2007). - S. Jelić, An FPTAS for the fractional group Steiner tree problem, Croatian Operational Research Review
**6**/2 (2015), 525-539This paper considers a linear relaxation of the cut-based integer programming formulation for the group Steiner tree problem (FGST). We combine the approach of Koufogiannakis and Young (2013) with the nearly-linear time approximation scheme for the minimum cut problem of Christiano et. al (2011) in order to develop a fully polynomial time approximation scheme for FGST problem. Our algorithm returns the solution to FGST where the objective function value is a maximum of $1+6varepsilon$ times the optimal, for $varepsiloninlangle0,1/6]$, in $tilde{O(mk(m+n^{4/3}varepsilon^{-16/3})/varepsilon^2)$ time, where $n$, $m$ and $k$ are numbers of vertices, edges and groups in the group Steiner tree instance, respectively. This algorithm has a better worst-case running time than algorithm by Garg and Khandekar (2002) where the number of groups is sufficiently large. - K. Elbassioni, S. Jelić, D. Matijević, The relation of Connected Set Cover and Group Steiner Tree, Theoretical Computer Science
**438**(2012), 96-101We report that the Connected Set Cover (CSC) problem is just a special case of the Group Steiner Tree (GST) problem. Based on that we obtain the first algorithm for CSC with polylogarithmic approximation guarantee as well as the first approximation algorithms for the weighted version of the problem and the version with requirements. Moreover, we argue that the inapproximability result of GST will carry on to the weighted version of the CSC problem.

### Projects

- “Paralelno računanje na grafičkom čipu u problemima diskretne linearne optimizacije”, (Odjel za matematiku, Sveučilište u Osijeku – Sveučilište u Osijeku) – voditelj projekta: Domagoj Matijević