Global QuickSearch:   Number of matching entries: 0

Search Settings

    Author / Editor / Organization Title Year Journal / Proceedings / Book BibTeX type DOI/URL
    Kápolnai, R.; Domokos, G. & Szeberényi, I. On the smallest parallel quadrangulation with minimum degree 3 2015 Workshop on the Advances of Information Technology , pp. 41-43   inproceedings  
    Abstract: The identity of the smallest quadrangulation with minimum degree 3 also containing parallel edges is unknown.
    However, it has already been determined that its order (the number of vertices) is between 11 and 14.
    This paper narrows this domain by showing that the order is at least 12.
    BibTeX:
    @inproceedings{kapolnai2015wait,
      author = {Richárd Kápolnai and Gábor Domokos and Imre Szeberényi},
      title = {On the smallest parallel quadrangulation with minimum degree 3},
      booktitle = {Workshop on the Advances of Information Technology},
      year = {2015},
      pages = {41--43}
    }
    					
    Kápolnai, R. Restricted Generation of Quadrangulations and Scheduling Parameter Sweep Applications 2014 School: Budapest University of Technology and Economics   phdthesis URL 
    BibTeX:
    @phdthesis{kapolnai2014phd,
      author = {Richárd Kápolnai},
      title = {Restricted Generation of Quadrangulations and Scheduling Parameter Sweep Applications},
      school = {Budapest University of Technology and Economics},
      year = {2014},
      url = {http://www.iit.bme.hu/~kapolnai/thesis/}
    }
    					
    Kápolnai, R. & Szeberényi, I. Scheduling Jobs and Batches Based on Historical Data 2013 International Journal of Computers and Communications
    Vol. 7 (3) , pp. 55-63  
    article URL 
    Abstract: This paper considers the problem of minimizing the
    makespan when scheduling jobs of unknown length on identical
    machines, meaning there is no a priori information on the job lengths.
    However, as the user of a parallel computational infrastructure is
    assumed to repeat the execution of the jobs multiple times and is
    able to measure individual machine completion times, a historical
    database is proposed to aid the approximation of the optimal schedule.
    We limit the size of this database so any set of jobs assigned to a
    machine has to be briefly described with limited data so an arbitrary
    feasible schedule may not be suitable.
    Two job models are studied: the Parameter Sweep Application
    (PSA) model which can be regarded as a set of jobs without
    dependency or inter-communication requirements, and the Batches
    of PSAs (BPSA) model where the jobs are executed in batches to be
    preceded by a sequence independent setup work.
    We propose an iterative framework which repeats computing an
    approximate schedule, executing the PSA or BPSA and updating
    the historical database according to the machine completion times.
    After each iteration, the approximation algorithm further improves
    some upper bound on the makespan until a 2-approximation is
    reached in case of PSA, 3-approximation in case of BPSA. The
    scheduling algorithm always assigns consecutive jobs called chains to
    machines keeping the historical database and the machine assignment
    descriptions brief.
    BibTeX:
    @article{kapolnai2013naun,
      author = {Kápolnai, Richárd and Szeberényi, Imre},
      title = {Scheduling Jobs and Batches Based on Historical Data},
      journal = {International Journal of Computers and Communications},
      year = {2013},
      volume = {7},
      number = {3},
      pages = {55--63},
      url = {http://www.naun.org/main/UPress/cc/c012002-168.pdf}
    }
    					
    Kápolnai, R.; Szeberényi, I. & Goldschmidt, B. Approximation of repeated scheduling chains of independent jobs of unknown length based on historical data 2013 Recent Advances in Computer Science , pp. 41-46   inproceedings URL 
    Abstract: We consider the problem of minimizing the makespan when scheduling a Parameter Sweep Application
    (PSA, set of independent jobs) on identical machines of a parallel computational infrastructure. However, there is
    no a priori information on the job lengths, and the user intends to execute the whole PSA multiple times and is
    able to measure individual machine completion times. We also require that any set of jobs assigned to a machine
    has to be briefly described so an arbitrary schedule may not be suitable.
    This paper proposes an iterative framework which repeats computing an approximation schedule, executing the
    PSA and updating the historical database according to the machine completion times. After each iteration, the
    approximation algorithm further improves some upper bound of the makespan until a 2-approximation is reached.
    The scheduling algorithm always assigns consecutive jobs called chains to machines keeping the historical database
    and the machine assignment descriptions brief.
    BibTeX:
    @inproceedings{kapolnai2013wseas,
      author = {Kápolnai, Richárd and Szeberényi, Imre and Goldschmidt, Balázs},
      title = {Approximation of repeated scheduling chains of independent jobs of unknown length based on historical data},
      booktitle = {Recent Advances in Computer Science},
      publisher = {WSEAS Press},
      year = {2013},
      pages = {41--46},
      url = {http://www.wseas.us/e-library/conferences/2013/Rhodes/COMPUTE/COMPUTE-04.pdf}
    }
    					
    Kápolnai, R.; Domokos, G. & Szabó, T. Generating spherical multiquadrangulations by restricted vertex splittings and the reducibility of equilibrium classes 2012 Periodica Polytechnica Electrical Engineering and Computer Science
    Vol. 56 (1) , pp. 11-20  
    article DOI  
    Abstract: We study the combinatorial properties associated with an earlier published, geometric algorithm capable of generating convex bodies in any primary equilibrium class (i.e. bodies with arbitrary numbers of equilibrium points) from a single ancestor. Primary equilibrium classes contain several topological secondary classes based on the arrangement of the equilibrium points. Here we show that the associated graph expansion algorithm is incomplete in the sense that using the same ancestor, not all secondary classes can be generated and we point out the nontrivial set of ancestors necessary to generate all secondary classes.
    BibTeX:
    @article{kapolnai2012periodica,
      author = {Kápolnai, Richárd and Domokos, Gábor and Szabó, Tímea},
      title = {Generating spherical multiquadrangulations by restricted vertex splittings and the reducibility of equilibrium classes},
      journal = {Periodica Polytechnica Electrical Engineering and Computer Science},
      year = {2012},
      volume = {56},
      number = {1},
      pages = {11--20},
      doi = {10.3311/PPee.7074}
    }
    					
    Kápolnai, R. & Domokos, G. Inductive generation of convex bodies 2011 The 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications , pp. 170-178   inproceedings  
    Abstract: Convex 3D bodies can be classified by the number of their stable and unstable equilibrium points. Inside these classes, we distinguish subclasses based on the topology of the equilibrium points defined by the Morse–Smale complex of the body. A topological subclass is equivalent to a vertex-coloured plane quadrilateral graph. Our first goal is to give the cardinality of some of these classes. Columbus expansions are specific geometric transformations perturbing the body only at the vicinity of an equilibrium point, such that they increase the number of either the stable or the unstable equilibrium points by one. Our second goal is determining which subclasses can be generated by these expansions from some ancestors. We choose the ancestors to be such irreducible subclasses which cannot be generated from any other subclass. In this paper, we give a characterisation of some of the irreducible subclasses, and an algorithm to determine the irreducible ancestor of any subclass. Due to the limited size of this abstract, we are planning to present the main ideas of our proofs and some other results only in the conference talk.
    BibTeX:
    @inproceedings{kapolnai2011hj,
      author = {Richárd Kápolnai and Gábor Domokos},
      title = {Inductive generation of convex bodies},
      booktitle = {The 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications},
      year = {2011},
      pages = {170--178}
    }
    					
    Kápolnai, R.; Domokos, G. & Szabó, T. Másodlagos egyensúlyi osztályok gráfelméleti származtatása 2011 XI. Magyar Mechanikai Konferencia   inproceedings  
    Abstract: (Rövidített változat.) Míg az elsődleges osztályok a stabil és instabil egyensúlyi pontokból alkotott (S,U) számpárral adhatóak meg, a másodlagos osztályokat az egyensúlyi pontok közötti heteroklinikus pályák alkotta Morse–Smale-komplex topológiája definiálja, melyeket formálisan egyensúlyi gráfokkal írhatunk le. Az itt vizsgált ún. Kolumbusz-lépések olyan műveletek, amelyek egy konvex testen geometriailag, és az ahhoz tartozó egyensúlyi gráfon kombinatorikailag egyaránt értelmezhetőek. Cikkünk azzal a kérdéssel foglalkozik gráfelméleti eszközökkel, hogy mely testek generálhatóak más testekből Kolumbusz-lépések sorozatával. A lépéssorozat kiindulásának ún. irreducibilis ősöket választunk, melyek semmilyen más gráfból nem generálhatóak. Bebizonyítjuk, hogy a Gömböc mellett végtelen sok irreducibilis gráf van, és ezek közé tartozik a tetraéder és a kocka egyensúlyi gráfja is. Ismertetjük számítógépes programunk futási eredményét, amellyel meghatároztuk a lehetséges alosztályok számát.
    BibTeX:
    @inproceedings{kapolnai2011mamek,
      author = {Kápolnai, Richárd and Domokos, Gábor and Szabó, Tímea},
      title = {Másodlagos egyensúlyi osztályok gráfelméleti származtatása},
      booktitle = {XI. Magyar Mechanikai Konferencia},
      year = {2011},
      note = {In Hungarian}
    }
    					
    Dóbé, P.; Kápolnai, R.; Sipos, A. & Szeberényi, I. Applying the Improved Saleve Framework for Modeling Abrasion of Pebbles 2010 Lecture Notes in Computer Science
    Vol. 5910 Large-Scale Scientific Computing , pp. 467-474  
    inproceedings DOI  
    Abstract: Saleve is a generic framework for making the developmentof Parameter Study tasks easy for scientists and engineers not familiarwith distributed technologies. In this paper we present our lightweightauthentication procedure for Saleve to delegate user credentials towardsthe grid. Then we present a detailed statistics of abrasion of pebblesgained with Saleve and note they are in accordance with the theoreticalresults. Finally we make remarks on the makespan of the application andlook for ways to reduce it.
    BibTeX:
    @inproceedings{dobe2010lssc,
      author = {Péter Dóbé and Richárd Kápolnai and András Sipos and Imre Szeberényi},
      title = {Applying the Improved Saleve Framework for Modeling Abrasion of Pebbles},
      booktitle = {Large-Scale Scientific Computing},
      publisher = {Springer},
      year = {2010},
      volume = {5910},
      pages = {467--474},
      doi = {10.1007/978-3-642-12535-5_55}
    }
    					
    Kápolnai, R. & Domokos, G. Morphology classes of convex bodies based on static equilibria. (Konvex testek egyensúlyi morfológiaosztályainak feltérképezése) 2010 Networkshop   inproceedings  
    Abstract: (Shortened version.) Two bodies belong into the same class if they have the same combination of the numbers of stable and unstable equilibrium points. For example, the body christened Gömböc has exactly one stable and one unstable equilibrium thus belongs to the class (1,1). The surface of the body determines connections between equilibrium points and we define subclasses in every class based on the topology of these connections. Our first goal is to design a combinatorial algorithm which is able to enumerate every possible subclass. Our second goal is to develop a parallel grid application which is able to do this in reasonable time. We present the structure and the operation of the grip application which we run in Hungrid.
    BibTeX:
    @inproceedings{kapolnai2010nws,
      author = {Richárd Kápolnai and Gábor Domokos},
      title = {Morphology classes of convex bodies based on static equilibria. (Konvex testek egyensúlyi morfológiaosztályainak feltérképezése)},
      booktitle = {Networkshop},
      year = {2010},
      note = {In Hungarian}
    }
    					
    Dóbé, P.; Kápolnai, R.; Sipos, A. & Szeberényi, I. Saleve: A Programming Framework for Scientific Parameter Study Problems 2009 EGEE Conference Poster  misc URL 
    Abstract: Saleve is a generic framework for making the development of Parameter Study tasks easy for scientists and engineers not familiar with distributed computing technologies. Saleve also makes it possible to migrate existing sequential programs in order to exploit the EGEE Grid. In this poster we wish to present three aspects of Saleve. First, we demonstrate its operation via a scientific pilot application. We simulate the abrasion process of a pack of pebbles and we explore detailed statistics about their final shapes over a range of parameters. Second, we present a lightweight delegation of credentials, which works without installing gLite or other third party software on the end users' computer. Third, we try to reduce the makespan of the jobs submitted by Saleve. We also outline some ideas for further improvements.
    BibTeX:
    @misc{dobe2009egee,
      author = {Péter Dóbé and Richárd Kápolnai and András Sipos and Imre Szeberényi},
      title = {Saleve: A Programming Framework for Scientific Parameter Study Problems},
      publisher = {EGEE'09 Conference},
      year = {2009},
      url = {http://indico.cern.ch/contributionDisplay.py?contribId=98&sessionId=137&confId=55893}
    }
    					
    Dóbé, P.; Kápolnai, R. & Szeberényi, I. Saleve: toolkit for developing parallel Grid applications 2008 Híradástechnika
    Vol. LXIII (1) , pp. 60-64  
    article URL 
    Abstract: We present the Saleve tool, which helps the migration of existing parameter study applications into grid environment. Programs linked against the Saleve library can be integrated into grids using different middleware systems, so the application developer need not deal with the technical details of the middleware.
    BibTeX:
    @article{dobe2008ht,
      author = {Péter Dóbé and Richárd Kápolnai and Imre Szeberényi},
      title = {Saleve: toolkit for developing parallel Grid applications},
      journal = {Híradástechnika},
      year = {2008},
      volume = {LXIII},
      number = {1},
      pages = {60--64},
      url = {http://hiradastechnika.hu/data/upload/file/2008/2008_1/HT_0801a-11.pdf}
    }
    					
    Dóbé, P.; Kápolnai, R. & Szeberényi, I. Simple Grid Access for Parameter Study Applications 2008 Lecture Notes in Computer Science
    Vol. 4818 Large-Scale Scientific Computing , pp. 470-475  
    inproceedings DOI  
    Abstract: The problem domain of Parameter Study covers a widerange of engineering and scientific tasks which can be easilyparallel. However, the research community users, who wouldlike to benefit from the supercomputing power of a Grid arenot familiar with the required distributed computingtechniques. For this reason, the presented Salèvedevelopment framework aims to free this limit by providing ageneral solution for PS tasks by inserting an abstractionlayer between the user application and the Grid middleware.We design a new Salève plugin for the gLite middleware ofthe EGEE Grid and discuss the authentication issues.
    BibTeX:
    @inproceedings{dobe2008lssc,
      author = {Péter Dóbé and Richárd Kápolnai and Imre Szeberényi},
      title = {Simple Grid Access for Parameter Study Applications},
      booktitle = {Large-Scale Scientific Computing},
      publisher = {Springer},
      year = {2008},
      volume = {4818},
      pages = {470--475},
      doi = {10.1007/978-3-540-78827-0_53}
    }
    					
    Dóbé, P.; Kápolnai, R. & Szeberényi, I. Saleve: Supporting the deployment of parameter study tasks in the Grid 2007 Cracow Grid Workshop , pp. 276-282   inproceedings  
    Abstract: We present Saleve, a developers’ tool to aid the creation of parallel running parameter study (PS) applications to run in distributed systems, batch schedulers or grids. Saleve enables the researchers to develop new parallel programs easily, without the need of knowing technical details of any specific middleware. The Saleve application can run either as a traditional sequential application or it can submit itself to the EGEE grid with the support of a Saleve server. In this paper we give a quick overview of the capabilities of Saleve, then we outline its operation. We also discuss our proposed solutions to the issues risen by the gLite plugin.
    BibTeX:
    @inproceedings{dobe2007cgw,
      author = {Péter Dóbé and Richárd Kápolnai and Imre Szeberényi},
      title = {Saleve: Supporting the deployment of parameter study tasks in the Grid},
      booktitle = {Cracow Grid Workshop},
      year = {2007},
      pages = {276--282}
    }
    					
    Dóbé, P.; Kápolnai, R. & Szeberényi, I. Saleve: párhuzamos grid-alkalmazások fejlesztőeszköze 2007 Híradástechnika
    Vol. LXII (12) , pp. 32-36  
    article URL 
    Abstract: A bemutatott Saleve rendszer párhuzamosan futó, ún. paraméterelemző alkalmazások fejlesztését és futtatását segítő eszköz. A Saleve-vel fejlesztett programokat változtatás nélkül integrálhatjuk különböző köztesrétegeket alkalmazó gridekbe, így az alkalmazás fejlesztőjének nem szükséges a köztesréteg technikai részleteit ismernie.
    BibTeX:
    @article{dobe2007ht,
      author = {Péter Dóbé and Richárd Kápolnai and Imre Szeberényi},
      title = {Saleve: párhuzamos grid-alkalmazások fejlesztőeszköze},
      journal = {Híradástechnika},
      publisher = {HTE},
      year = {2007},
      volume = {LXII},
      number = {12},
      pages = {32--36},
      note = {In Hungarian},
      url = {http://hiradastechnika.hu/data/upload/file/2007/2007_12/HT_0712-8.pdf}
    }
    					
    Németh, D.; Kápolnai, R. & Szeberényi, I. Grid az oktatásban 2007 Networkshop   inproceedings  
    Abstract: Budapest University of Technology and Economics (BME) –amongst some Hungarian members – participates in the EGEEproject, which is the major Grid project in Europe, led byCERN. Therefore we add to the EGEE infrastructurecomputational and storage resources already used by researchand educational activities at the university. Our sharedresources that are integrated to the EGEE infrastructure aredesigned to be scalable and easy-to-manage. Scalabilityappears in the simplicity of connecting additional resourcesand load balance. Easy management is brought by centralconfiguring and monitoring. Assuming that the EGEE middleware(gLite) and the security infrastructure need to be installedon all worker nodes, the design of this system is far morecomplex than that of traditional clusters. We provide anopportunity for the BME students to study Grid systems intheory, and our infrastructure in practice in lab as well bysubmitting simple jobs. Since Grid users usually access to theservices via virtual organizations, we created one for the ourstudents. In this paper we present the infrastructure built atthe department, then we demonstrate the working by followingthe life cycle of a sample application, and we summarize ourexperiences came up during the development of the system.
    BibTeX:
    @inproceedings{kapolnai2007nws,
      author = {Dénes Németh and Richárd Kápolnai and Imre Szeberényi},
      title = {Grid az oktatásban},
      booktitle = {Networkshop},
      year = {2007},
      note = {In Hungarian}
    }
    					
    Kis, T. & Kápolnai, R. Approximations and auctions for scheduling batches on related machines 2007 Operation Research Letters
    Vol. 35 (1) , pp. 61-68  
    article DOI  
    Abstract: We consider the scheduling of groups of identical jobs on related machines with sequence independent setup times. We provide a 2-approximation algorithm for minimizing the makespan. The second result is a truthful, polynomial time, randomized mechanism for the batch scheduling problem with a deterministic approximation guarantee of 4.
    BibTeX:
    @article{kis2007orl,
      author = {Tamás Kis and Richárd Kápolnai},
      title = {Approximations and auctions for scheduling batches on related machines},
      journal = {Operation Research Letters},
      publisher = {Elsevier},
      year = {2007},
      volume = {35},
      number = {1},
      pages = {61--68},
      doi = {10.1016/j.orl.2006.01.005}
    }
    					
    Kápolnai, R. Hálózattervezés nem kooperatív résztvevők számára (Network Design for Non-Cooperative Users) 2006 School: Budapest University of Technology and Economics (BME)   mastersthesis URL 
    Abstract: Motivated by Tim Roughgarden's book Selfish Routing and the Price of Anarchy (see: http://theory.stanford.edu/~tim/). We investigate a traffic network where users seek to minimizetheir own travel time. It seems reasonable to suppose that thetravel time along a path may depend on the amount of trafficrouted on it. The users choose their routes selfishly and individually, and this behaviour drives the system to a Nash equilibrium state in which no user intends to reroute itself to another path. Nevertheless, if all of the users were coordinated by a central authority, which aims at optimizing the public benefit, i.e. minimizing the total travel time, animproved performance of the network would be achieved. This loss of performance is called the price of anarchy (or coordination ratio). According to the recent results, computing the price of anarchy in congestion-sensitive traffic networks is possible. Additionally, one can reduce the price of anarchy by manipulating the network in several ways. Surprisingly, the total travel time induced by selfish users can be lowered byremoving edges from the network. The phenomenon is called Braess' paradox. Given a network, how could someonefind the harmful edges whose removal will improve the public benefit? There is no easy answer, because even the approximation of the underlying optimization problem is NP-hard. In this thesis, first we provide a quick overview of the theoretical background. Then we introduce an exact solution method for the network design problem above and present some experimental test results of the implementation. Our approachis based on a branch and bound algorithm, and we compare a few branching and selection rules by their performance.
    BibTeX:
    @mastersthesis{kapolnai2006halozat,
      author = {Richárd Kápolnai},
      title = {Hálózattervezés nem kooperatív résztvevők számára (Network Design for Non-Cooperative Users)},
      school = {Budapest University of Technology and Economics (BME)},
      year = {2006},
      note = {In Hungarian},
      url = {http://www.iit.bme.hu/~kapolnai/pub/kapolnai2006master.pdf}
    }
    					
    Kis, T. & Kápolnai, R. A 2-approximation algorithm and a truthful mechanism for scheduling batches on machines running at different speeds 2005 7th Workshop on Models and Algorithms for Planning and Scheduling Problems , pp. 157-160   inproceedings  
    BibTeX:
    @inproceedings{kis2005mapsp,
      author = {Tamás Kis and Richárd Kápolnai},
      title = {A 2-approximation algorithm and a truthful mechanism for scheduling batches on machines running at different speeds},
      booktitle = {7th Workshop on Models and Algorithms for Planning and Scheduling Problems},
      year = {2005},
      pages = {157--160}
    }