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
[BibTeX] |
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
[BibTeX] |
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} } |