Slobodan Jelić

 

Asistant Professor
Department of Mathematics
Josip Juraj Strossmayer University of Osijek
Trg Ljudevita Gaja 6
Osijek, HR-31000, Croatia¸
phone: +385-31-224-858
fax: +385-31-224-801
email:  Ova e-mail adresa je zaštićena od spambota. Potrebno je omogućiti JavaScript da je vidite.
office:  8 (ground floor)

 


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)

 

Journal Publications

  1. S. Jelić, D. Ševerdija, Government Formation Problem, Central European Journal of Operations Research (2017), prihvaćen za objavljivanje
    In 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.
  2. 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-875
    We 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).
  3. S. Jelić, An FPTAS for the fractional group Steiner tree problem, Croatian Operational Research Review 6/2 (2015), 525-539
    This 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.
  4. K. Elbassioni, S. Jelić, D. Matijević, The relation of Connected Set Cover and Group Steiner Tree, Theoretical Computer Science 438 (2012), 96-101
    We 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.


Refereed Proceedings

  1. S. Jelić, On the fractional group Steiner tree problem, SYM-OP-IS 2015: XLII International Symposium on Operations Research, Donje Gradište, 2015
  2. S. Jelić, D. Matijević, The relation of Connected Set Cover and Group Steiner Tree, Conference on Applied Mathematics and Scientific Computing 2011, Trogir, 2011
    Let $U$ be the universe of elements which have to be covered, $mathcal{S}$ family of subsets of $U$ and $G=(mathcal{S},E)$ connected graph on vertex set $mathcal{S}$. We say that subfamily $mathcal{R}subseteqmathcal{S}$ is emph{connected set cover} (CSC) if every $uin U$ is covered by at least one set from $mathcal{R}$ and subgraph $G[mathcal{R}]$ induced by $mathcal{R}$ is connected. The problem is to find connected set cover with respect to $(U,mathcal{S},G)$ with minimum number of sets (vertices). On the other hand, suppose that we are given a graph $G$ with edge weight function $w:E(G)rightarrowR^+$ and family of subsets of vertices $mathcal{G} = {g_1,g_2,ldots,g_k},quad g_isubset V$ which will be called groups. The well known and well studied emph{Group Steiner Tree} (GST) is to find a subtree $T$ that minimizes the weight function $sum_{ein E(T)}w(e)$ such that $V(T)cap g_ineqemptyset$ for all $iin{1,ldots,k}$. We showed in our work that CSC is equivalent to the variant of GST when all edge weights equal to $1$. Hence, all algorithms for GST immediately apply for CSC problem as well. As a result, we obtain an approximation algorithm for CSC problem with approximation ratio $O(log^2mloglog mlog n)$ where $n$ is the size of universe $U$ and $m$ is the size of family $mathcal{S}$. This is the first polylogarithmic approximation algorithm for CSC problem. Natural generalization of CSC problem is to associate the nonnegative weight function with sets in $mathcal{S}$. Weighted CSC problem assumes finding of connected set cover that minimizes the total weight of subfamily $mathcal{R}$. We showed that this problem can be solved by reduction to the fault-tolerant version of Group Steiner problems for which $O(sqrt{m}log m)$ approximation algorithm is known. We also consider generalization of CSC problem where each element $u$ from universe has requirement $r_u$ on number of sets covering element $u$ associated. We showed the reduction of this problem to the variant of GST problem with requirements associated to the groups for which $O(log^2 mloglog mlog(Rcdot n))$ approximation algorithm is known, where $R$ dentes the largest requirement.


Others

  1. D. Matijević, D. Ševerdija, S. Jelić, L. Borozan, Uparena optimizacijska metoda, Math.e : hrvatski matematički elektronski časopis 30 (2016)
    U ovom članku analiziramo metode gradijentnog i zrcalnog spusta u području konveksne optimizacije s danim naglaskom na njihove brzine konvergencije. Nadalje, uparujući dvije spomenute metode dobivamo takozvanu uparenu metodu čija analiza konvergencije pokazuje ubrzanje u odnosu na gradijentnu i zrcalnu metodu, te bilo koju drugu nama poznatu metodu prvoga reda.
  2. Z. Ivančević, S. Jelić, Primjena SVD rastava matrice u dohvatu informacija i kompresiji slike, Osječki matematički list (2015), prihvaćen za objavljivanje
  3. S. Jelić, Primjena karakterističnih funkcija u statistici, Osječki matematički list 10/1 (2010), 85-94
    U ovom radu određene su funkcije distribucije aritmetičke sredine slučajnog uzorka duljine n iz standardne normalne i jedinične uniformne distribucije primjenom karakterističnih funkcija. Na primjeru geometrijske sredine uzorka iz jedinične uniformne distribucije ilustrirana je primjena teorijskih rezultata o karakterističnim funkcijama (teorem jedinstvenosti). Navedeni su i specijalni primjeri određivanja distribucija nekih statistika koje se često primjenjuju.
  4. S. Jelić, D. Matijević, Stage Illumination Problem (2009)
    Consider the following illumination problem: given a stage represented by a horizontal line segment and a set of light sources represented by a set of points in the plane above, assign powers to the light sources such that every point on the stage receives a sufficient amount (say one unit) of light while minimizing the overall power consumption. Under the assumption that the amount of light arriving from a fixed light source decreases rapidly with the distance from the light source, this becomes an interesting optimization problem. Two approximation algorithms based on linear programming are used in this Demonstration.



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ć

 


Teaching

 Konzultacije: Srijeda, 11:00 - 12:00

 

Nastavne aktivnosti u zimskom semestru:

Nastavne aktivnosti u ljetnjem semestru:

Teme diplomskih radova

  • Algoritmi preslikavanja XML modela u objektno-relacijski model podataka (u suradnji s IN2) (PDF)
  • Preslikavanja XML modela u objektno-relacijski model podataka pomoću suvremenih sustava za upravljanje bazama podataka (u suradnji s IN2) (PDF)
  • Modeli procjene rizika u upravljanju projektima (u suradnji s IN2) (PDF)
  • Model za formiranje ekspertnih timova u upravljanju projektima (u suradnji s IN2) (PDF)
  • Relacijski model baze podataka za mobilnu prodaju i praćenje agenata (u suradnji s Adacta-om) (PDF)

Teme završnih radova

  • Teme završnih radova iz kolegija Uvod u vjerojatnost i statistiku (DOC)
  • Teme završnih radova iz kolegija Uvod u strukture podataka i algoritme (DOC)

Personal