Duality in Graph Theory, in Matroid Theory and in Electric Network Theory

András Recski

Budapest University of Technology and Economics

In the first part of the talk we give a short (and probably incomplete) survey of the history of duality -- what did the Greeks like Pythagoras and Theaetetus know 2500 years ago (within the framework of regular polyhedra), what were the contributions of Descartes in the 17th century (within the framework of analytic geometry), what happened 200 years ago in the theory of convex polyhedra (Lhuilier), how graph and matroid theorists joined the scene some 120 and 80 years ago, respectively? We shall also emphasize that physicists and engineers (Kirchhoff, Maxwell, Cremona) of the 19th century did remarkable contributions to the more or less proper undertanding of these concepts.

Then we switch to the last half-century and show that the advent of the more complex electric devices raised new questions in the theory of linear systems. Using some very simple examples (no preliminary knowledge in electric network theory is required) we conclude (Iri and Recski, 1980, Recski, 2013) that two different voltage-current symmetries exist in electric network theory.

A projection hierarchy for some NP-hard optimization problems

Franz Rendl

Alpen-Adria Universität Klagenfurt, Austria

There exist several hierarchies of relaxations which allow to solve NP-hard combinatorial optimization problems to optimality. The Lasserre and Parrilo hierarchies are based on semidefinite optimization and in each new level both the dimension and the number of constraints increases. As a consequence even the first step up in the hierarchy leads to problems which are extremely hard to solve computationally for nontrivial problem sizes.

In contrast, we present a hierarchy of semidefinite relaxations where the matrix dimension stays fixed and only the number of constraints grows exponentially. It applies to downward monotone problems. We consider this new hierarchy for Max-Cut, Stable-Set and Graph-Coloring. The starting point in case of Max-Cut is the semidefinite relaxation over the set of correlation matrices. For Stable-Set it is based on the Lovasz theta function in 'primal form' and for Coloring, we use the 'dual form' of the theta function as a starting point. We introduce a generic separation procedure identifying inexact subgraphs. It is based on copositivity and exploits the fact that all these problems have relaxations lying in the cone of completely positive matrices. We provide computational results for all three problem types.

The Red-Blue Transportation Problem

Dries Goossens¹, Federico Della Croce², Frits C. R. Spieksma³, Wim Vancroonenburg⁴

¹Ghent University, Faculty of Economics and Business Administration, Gent (Belgium)
²Politecnico di Torino, D.A.I., Torino (Italy)
³KU Leuven, Faculty of Business and Economics, ORSTAT, Leuven (Belgium)
⁴KU Leuven, Department of Computer Science, CODeS & iMinds-ITEC, Gent (Belgium)

In this contribution, we generalize the transportation problem by associating a color, either red or blue, to each supply node. Thus, the set of supply nodes is partitioned into two sets R (red) and B (blue) such that each supply node gets precisely one color. The additional requirement is that the set of supply nodes that actually supply a demand node should all have the same color. In other words, a demand node is only allowed to receive flow from supply nodes that are either all red or all blue. We will refer to this problem as the Red-Blue Transportation Problem (Red-Blue TP).

Consider a setting where patients in a hospital need to be assigned to rooms. Rooms are of limited capacity, and due to specific equipment, not all rooms are equally appropriate for each patient. For instance, a patient's pathology may require oxygen to be available at the room; rooms that do not meet this requirement, need to be equipped with a mobile oxygen supply which is, for organizational reasons, less desirable. In this setting, patients must be assigned to rooms in a way that the medical concerns and personal wishes are fulfilled as much as possible, and such that male and female patients are not assigned to the same room. Clearly, this situation can be modeled as a (special case of) Red-Blue TP.

We settle the complexity status, showing that Red–Blue TP is NP-hard, and a constant-factor approximation is not likely to exist, even in a number of special cases. We discuss two integer programming formulations: although we can show that one formulation is strictly stronger than the other, experimental results show that the stronger formulation requires increasingly more computation time than the weaker formulation, as the problem size, the percentage of red nodes, or the density of the graph increase.

We also consider a maximization variant of Red–Blue TP, which is interesting with respect to approximation. We develop three approximation algorithms, each of which guarantee an approximation ratio of ½, and we conduct a computational study on the performance of these algorithms on randomly generated instances.

Finally, we discuss a number of generalizations of Max-Red–Blue TP, including a variant with K colors.

Optimization models for railway freight transportation

Tibor Illés

Department of Differential Equations, Budapest University of Technology and Economics

Although freight and passenger railway transportation has many common features there is at least one major difference, namely, there is no time table for railway freight transportation in the sense as for passenger railway transportation. For railway freight transportation instead of time tables there are time table of planned freight trains with quite flexible rules of changing those in case of available capacities for railway transportations.

Railway freight transportation is based on orders rather than precise time tables. The orders for a freight train could be changed even few hours before the leaving time of a freight train.
The models and methods that are presented in this talk have been developed during a project sponsored by MÁV Trakció Zrt. (part of the MÁV Group). MÁV – The Hungarian State Railway Company gave us lots of data for railway freight transportation. We have got data for orders of freight trains from the planning period and data of those freight trains that were running in the analyzed period, as well.

The research questions of the project were the following ones: under uncertain conditions that the possible changes of ordered freight trains might causes develop models for (i) planning the train and duty assignments for a month, (ii) due to the fact that the changes in ordered trains are quite regular develop re-optimization model for train assignment.

In this talk we focus on planning and re-optimization models for train assignment and discuss similarities and differences between these models.

Finally, we illustrate our models and methods with some computational results on real-life problem instances.

Heuristic and exact algorithms for the interval min-max regret knapsack problem

Silvano Martello, F. Furini, M. Iori, M. Yagiura

We consider a generalization of the 0-1 knapsack problem in which the profit of each item can take any value in a given range. A set of specic profits is called a scenario. Each feasible solution associated with a scenario has a regret, given by the difference between the optimal solution value and the value of the considered solution. The interval min-max regret knapsack problem (MRKP) is then to nd a feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a practical point of view. Its decision version is most probably not in NP, and even computing the regret of a solution with respect to a scenario requires the solution of an NP-hard problem. We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP. We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm, and evaluate their performance through extensive computational experiments.

Strong Stability of Nash Equilibria in Load Balancing Games

Bo Chen

Centre for Discrete Mathematics and Its Applications, Warwick Business School, University of Warwick

We study strong stability of Nash equilibria in load balancing games of m (m ≥ 2) identical servers, in which every job chooses one of the m servers and each job wishes to minimize its cost, given by the workload of the server it chooses.

A Nash equilibrium (NE) is a strategy profile that is resilient to unilateral deviations. Finding an NE in such a game is simple. However, an NE assignment is not stable against coordinated deviations of several jobs, while a strong Nash equilibrium (SNE) is. We study how well an NE approximates an SNE.

Given any job assignment in a load balancing game, the improvement ratio (IR) of a deviation of a job is defined as the ratio between the pre- and post-deviation costs. An NE is said to be a ρ-approximate SNE (ρ ≥ 1) if there is no coalition of jobs such that each job of the coalition will have an IR more than ρ from coordinated deviations of the coalition.

While it is already known that NEs are the same as SNEs in the 2-server load balancing game, we prove that, in the m-server load balancing game for any given m ≥ 3, any NE is a (5/4)-approximate SNE, which together with the lower bound already established in the literature yields a tight approximation bound. This closes the final gap in the literature on the study of approximation of general NEs to SNEs in load balancing games. To establish our upper bound, we make a novel use of a graph-theoretic tool.

Scheduling two uniform machines with known optimum: tight results

György Dósa

We revisit the semi online problem of scheduling two uniform machines minimizing the makespan, with the knowledge of the optimum value.

We give tight competitive ratios for some values of the speed ratio s of the machines.

First Leah Epstein considered this problem in 2003, and gave lower bounds and two algorithms, getting the tight ratio in certain intervals, and not touching lower and upper bounds (i.e. gaps) in another places. The similar semi online problem when the total size of the jobs is known, was investigated …first by Zsolt Tuza and his coauthors, in 2004. After these works two intervals remained (a left and a right interval for short), where the tight ratio was not known.

In 2009 Zhiyi Tan and his coauthors considered the right interval, and gave improved results, but some gaps still remained in almost all places within the interval. The left interval was considered by Dosa, Speranza and Tuza in 2011. In both these papers both semi online conditions were treated, as it turned out that they can be handled similarly. In the left interval both semi online problems are solved. Now we consider the right interval.

We conjecture that more difficult lower bound constructions were never applied for similar problems. The case is similar to some thriller. First the players make some small mistake. To hide it, they make a new mistake, bigger than the …first one, and so on. Now the case is more happy: the lower bound construction starts with small, then a bit larger, and fi…nally larger and larger jobs. The result is a bad competitive ratio that any algorithm must have.

On the other hand, we also give a new algorithm, which also owns some interest. As a result, we get know the tight competitve ratios in several places within the interval.

The Modular Tool Switching Problem

Csaba Raduly-Baka

University of Turku

The problem of minimizing the number of tool switches for a single numerically controlled machine, with a modular tool magazine, is considered. A set of jobs are processed with the machine. Each job requires a specific set of tools to be present in the machine. The machine has a tool magazine with limited capacity, sufficient to process individual jobs, yet insufficient to hold all the tools required for the set of jobs, requiring tool changes between consecutive jobs.

The tool switching problem also arrises in the assembly of printed circuit boards (PCB), where flexible component placement machines are used to mount components onto a bare PCBs.

In the case of a fixed job sequence and a non-modular feeder unit, the problem of switching component reels (of equal size) can be solved efficiently and optimally. We show that if the placement machine is of modular type, the component reel (tool) switching becomes NP-hard for the general case (arbitrary module capacity and/or module count). We also show, that if both the module capacity and the number of modules are fixed, the problem can be solved optimally in polynomial time, albeit with a very large exponent.

Fractal automata

Benedek Nagy

Regular languages can be represented by finite state acceptors (finite automata) and by (special restricted form of) railroad diagrams (also called syntax diagrams). These two concepts are closely related, a kind of graph-transformation algorithm can be used to connect them in each directions.

Context-free languages can also be described by (the general form, i.e. sets of) railroad diagrams allowing non-terminals. Based on the analogy, using similar type of graph-transformation a new type of automata, the fractal automata are obtained. They accept exactly the context-free languages, that can be shown by relations between the pushdown automata and fractal automata. This new type of automata highlight the difference of the regular and context-free languages in a visual way: the possibility of recursions at context-free case.

Automated Employee Scheduling

Nysret Musliu

Finding appropriate employee schedules is of great importance, because the work schedules influence the lives of employees, and the organizations in the commercial and public sector must meet their workforce requirements and ensure the quality of their services and operations. However, this is a tremendously complex task due to the huge number of constraints that have to be fulfilled (e.g. labor rules, individual employee preferences, and requirements of companies) and the enormous search space of possible solutions. Such complex problems appear especially in companies where the required number of employees throughout the time periods fluctuates, which operate 24 hours per day, and deal with critical tasks.

General employee scheduling problems have been mainly solved in separated phases which include several sub-problems, each of which are NP-hard (e.g., shift scheduling, break scheduling, workforce scheduling, etc.). Due to the difficulty of these problems, the human experts can construct good solutions only for very small problems. Therefore, researchers from the area of Operations Research, and later also Artificial Intelligence have been working on solving different employee scheduling for more than 40 years.

In this talk we will first introduce different employee scheduling problems and describe their main characteristics. In the second part, we will discuss the state-of-the-art techniques that have been proposed to solve these problems. These methods include complete algorithms, metaheuristic techniques and hybrid methods. Finally, we will show the application of some techniques in real-life problems and describe the remaining challenges in employee scheduling.

On the auxiliary algorithm of coloring

Bogdan Zavalnij

In the NP-hard problem of maximum clique search the auxiliary algorithm of graph coloring proved to be of great help. Maximum clique search is usually completed with the aim of some Branch-and-Bound technique, where coloring provides bounds through upper estimates and sometimes branching rule as well.

In the first part of my talk I would like to introduce an extended version of the long well known graph coloring: the s-free coloring. I will show the superiority of the new method to the old one and the connection of these methods. Actual measurements with hard case graphs will be provided as well.

In the second part I would like to widen the actual usability of coloring. Instead of searching maximum cliques in graphs the s-free coloring, as I try to introduce, could be used as an auxiliary algorithm in various other hard discrete optimization problems where we are using some Branch-and-Bound technique. I would like to show the possible usage of this method in maximum weighted clique search; maximum transitive tournament search; 0-1 and ILP; and SAT and MaxSAT problems. Obviously, the "coloring" should be redefined, but the main principles and usability will be quite similar.

Spanning Tree Game as Prim Would Have Played

Andras Pluhar (joint work with Andras London)

We investigate special types of Maker-Breaker games defined on deterministic graphs where Maker's goal is to get a spanning tree. If the moves are arbitrary this is the well-known Shannon's switching game for which Lehman gave a characterization that turned out to be fairly influential for the development of matroid theory. Maker wins if the graph G contains two disjoint spanning trees.

Here we restrict Maker's possible moves that resembles to the way that was introduced by Espig, Frieze, Krivelevich and Pedgen. We require that the subgraph induced by Maker's edges must be connected throughout the game. Besides the normal play we consider the biased and accelerated versions of these games.

The normal game can be characterized, surprizingly, both player's best strategies are pairing strategies. The biased game, where Maker takes a, Breaker takes b edges in each step are more difficult, and if e.g. a=1 and b=2 it does not follow the probabilistic intuition. However, if a > 1, the probabilistic intuition applies again, as our main result shows:

Playing the (2:b) PrimMaker-Breaker game on K_n, Maker wins if b < n/(8 log n), and there exists K > 0 such that Breaker wins if b > Kn/log n.

Simplified Simulated Annealing metaheuristic for the Capacitated Location Routing Problem

Karlo Bala, Nebojša Gvozdenović

We present an algorithm for solving the Capacitated Location Routing Problem based on a Simplified Simulated Annealing metaheuristic. This algorithm uses a special data structure for coding CLR problems, a single universal transformation and single input parameter. The proposed algorithm has been tested with various input parameter values on three standard benchmark problem sets. The results showed that the proposed approach has a good time/quality ratio and it is competitive with other state of the art algorithms.

A Robust AFPTAS for Online Bin Packing with Polynomial Migration

Kim-Manuel Klein, Klaus Jansen

In this paper we develop general LP and ILP techniques to find an approximate solution with improved objective value close to an existing solution. The task of improving an approximate solution is closely related to a classical theorem of Cook et al. in the sensitivity analysis for LPs and ILPs. This result is often applied in designing robust algorithms for online problems. We apply our new techniques to the online bin packing problem, where it is allowed to reassign a certain number of items, measured by the migration factor. The migration factor is defined by the total size of reassigned items divided by the size of the arriving item. We obtain a robust asymptotic fully polynomial time approximation scheme (AFPTAS) for the online bin packing problem with migration factor bounded by a polynomial in 1/ε. This answers an open question stated by Epstein and Levin in the affirmative. As a byproduct we prove an approximate variant of the sensitivity theorem by Cook at el. for linear programs.
This is joint work with my PhD student Kim-Manuel Klein.

Large Forbidden Cofigurations and Design Theory

Attila Sali¹, Richard Anstee²

¹Rényi Institute ²UBC, Vancouver

A simple matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix F, we say that a (0,1)-matrix A has F as a configuration if there is a submatrix of A which is a row and column permutation of F (trace is the set system version of a configuration). Let ∥A∥ denote the number of columns of A. We define forb(m; F) = max{∥A∥ : A is m-rowed simple matrix and has no configuration F}. Let t ⋅ F denote the concatenation of t copies of F.

We explore cases where forb(m; t ⋅ F) can be determined, where t is allowed to be a function of m. Extremal constructions are obtained by application of recent design theory results.

A Best Possible Algorithm for Semi-Online Scheduling

Hans Kellerer¹, Michaël Gabay², Vladimir Kotov³

¹Institut für Statistik und Operations Research, Universität Graz, Universitätsstraße 15, A{8010 Graz, Austria, hans.kellerer@uni-graz.at
²Grenoble-INP / UJF-Grenoble 1 / CNRS, G-SCOP UMR5272 Grenoble, F-38031, France, michael.gabay@g-scop.grenoble-inp.fr
³Belarussian State University, Faculty of Applied Mathematics and Computer Science, Nezavisimosty ave. 4, Minsk, 220030, Belarus, kotovVM@bsu.by

The well-known classical multiprocessor scheduling problem is a fundamental and well-investigated scheduling problem both in the offline and the online setting. A set of n independent jobs is to be processed on m parallel, identical machines in order to minimize the makespan. We consider online multiprocessor scheduling with the additional assumption that the sum of processing times is given in advance. The resulting problem is denoted as the semi-online scheduling problem.

In [2] Cheng, Kellerer and Kotov presented an algorithm with performance ratio 1.6 for semi-online scheduling for an arbitrary number of machines. Moreover, they established a lower bound of 1.5 for m ≥ 6 machines. Recently, Albers and Hellwig [1] developed an improved lower bound showing that no deterministic semi-online algorithm for semi-online scheduling can attain a competitive ratio smaller than ≈1.585 when m tends to infinity. Moreover, they give a simple algorithm with performance ratio 1.75.

In this talk we will present an algorithm with competitive ratio ≈1.585 for semi-online scheduling, which is equal to the lower bound of Albers and Hellwig. Thus, our algorithm is best possible for large values of m.

Our algorithm classifies jobs and machines and runs in two phases. In the first phase, jobs are assigned to the machines depending on jobs and machines classes. In the second phase we distinguish two cases depending on the structure of the machines after Phase 1 and for each case a separate algorithm is presented.

[1] S. Albers, M. Hellwig, Semi-online scheduling revisited, Theoretical Computer Science 443 (2012) 1-9.

[2] T.C.E. Cheng, H. Kellerer, V. Kotov, Semi-on-line multiprocessor scheduling with given total processing time, Theoretical Computer Science 337 (2005) 134-146.

The optimal absolute ratio for online bin packing

Rob van Stee, János Balogh, József Békési, György Dósa, Jiri Sgall

In the online bin packing problem, a sequence of items with sizes in the interval (0,1] arrive one by one and need to be packed into bins, so that each bin contains items of total size at most 1. Each item must be irrevocably assigned to a bin before the next item becomes available. The algorithm has no knowledge about future items. There is an unlimited supply of bins available, and the goal is to minimize the total number of used bins (bins that receive at least one item). We present an online bin packing algorithm with absolute competitive ratio 5/3, which is optimal.

Largest union-intersecting families

Gyula O.H. Katona, Dániel T. Nagy

MTA Rényi Institute, Budapest

János Körner asked the following question. Let [n] = {1, 2, ... n} and let Ƒ ⊂ 2^[n] be a family of its subsets. It is called union-intersecting if (F₁ ∪ F₂) ∩ (F₃ ∪ F₄) is non-empty whenever F₁, F₂, F₃, F₄ ∈ Ƒ and F₁ ≠ F₂; F₃ ≠ F₄. What is the maximum size of a union-intersecting family? This question is answered in the present paper. The optimal construction when n is odd consists of all subsets of size at least (n-1)/2 while in the case of even n it consists of all sets of size at least n/2 and sets of size n/2-1 containing a fixed element, say 1. We also proved some extensions, variants and analogues of this statement. The following one is an example. Suppose that Ƒ is a union-intersecting family of k-element subsets of [n]. We found that the optimal construction for this problem consists of all k-element subsets of size k containing the element 1, and one more additional set, if for n > n(k). The results were jointly achieved with Dániel T. Nagy.

Recent Applications of Supermodular Functions

András Frank

Department of Operations Research, Eötvös University Budapest

In 1995, Frank and Jordán proved a general min-max formula concerning the minimum covering of supermodular bi-set functions by digraphs. The result provided a solution to the optimal directed edge-connectivity and node-connectivity augmentation problems, implied an extension of Győri’s deep theorem on optimal coverings of vertically convex polyominos by rectangles, and gave rise to a min-max result on the maximum K_t,t-free t-matchings of a bipartite graph.

In the present work, we explore two recent applications. The first one describes a necessary and sufficient condition for the existence of k disjoint spanning arborescences F₁, F₂, . . . , F_k of root r₀ in a digraph D so that the number of roof-edges of F_i is m_i for i = 1, 2, . . . , k where m₁,m₂, . . . ,m_k are specified positive integers. The other application is a necessary and sufficient condition for the existence of a k-node-connected simple digraph for which both the in-degree and the out-degree of each node are specified numbers.

Proof complexity and the Lovasz-Kneser Theorem

Gabriel Istrate

We investigate the proof complexity of a class of propositional formulas expressing a combinatorial principle known as the Kneser-Lovasz Theorem. This is a family of propositional tautologies, indexed by an nonnegative integer parameter k that generalizes the Pigeonhole Principle (PHP, obtained for k=1).

We show for all fixed k 2^ω(n) lower bounds on resolution complexity and exponential lower bounds for bounded depth Frege proofs. These results hold even for the more restricted class of formulas encoding Schrijver's strengthening of the Kneser-Lovasz Theorem. On the other hand for the cases k=2,3 (for which combinatorial proofs of the Kneser-Lovasz Theorem are known) we give polynomial size Frege (k=2), respectively extended Frege (k=3) proofs. We conclude with a brief discussion of the results (that will be presented in a subsequent paper) on the complexity of the general case of the Kneser-Lovasz theorem.

Based with joint work with Adrian Craciun and subsequent unpublished results with several authors.

Ordering Problems

Gerhard Reinelt

Ruprecht-Karls-Universität Heidelberg, Germany

Many combinatorial optimization problems are concerned with the determination of optimal orderings of objects subject to various types of constraints and objectives. In particular, the objective function has a big influence on the difficulty of an ordering problem and on suitable optimization algorithms. In this talk we survey some of these problems and report about approaches for solving them to optimality.

Distance matrix generation via linear road sampling

Nebojša Gvozdenović, Karlo Bala, Saša Bošnjak, Nenad Mirkov

We deal with data describing road routes between many to many geographical points (geopoints) provided by a black box for road routing. The black box takes two geographical points as an input, and generates the shortest path as an array of manoeuvre points and distances between consecutive points in it. The goal is to generate shortest distance matrix for n given points. A single call of the black box incurs unit costs, hence determining distances via "all pairs" approach costs n²-n. We propose a method based on geographical orientations that leads to determining nearly optimal routes while generating linear costs. We show experimentally that the time distance matrix obtained via our algorithm is almost identical to the matrix generated via "all pairs" approach.

Locating Low Rank Submatrices of a Matrix

Sándor Szabó

If a given matrix can be well approximated by another matrix of rank at most two, then the information summarized in the original matrix can be transformed into a 2-dimensional plot. This in turn opens up the possibility of a visual inspection. This is a widely used technique in exploratory data analysis. Instead of approximating the whole given matrix with a low rank matrix we propose to locate low rank (rank 1 or rank 2) possible large size submatrices in the given matrix. The purpose again is to make the information contained by the original matrix available for a visual inspection. Many times the whole matrix cannot be replaced by a low rank matrix in a reasonable manner. This means that the data set cannot be visualized globally. However, the data set may well contain 1-dimensional or 2-dimesional clearly identifiable substructures. The computations are related to a graph model. One method is based on finding large cliques in a suitable constructed graph. A further technique utilizes a legal or well coloring of the edges of a graph. Since in the intended typical applications we are keeping in mind the occurring graphs are relatively large: Consequently the clique search and coloring algorithms we apply are greedy algorithms giving only suboptimal solutions instead of verifiable optimal solutions.

Search for Hamiltonian Cycles, The Behaviour of the Sufficient Conditions

Csongor Csehi (joint work with János Tóth)

Budapest University of Technology and Economics

Determining whether Hamiltonian cycles exist in graphs is an NP-complete problem. The theorems of Dirac, Ore, Pósa and Chvátal provide easy-to-check sufficient conditions for the existence of such cycles. Some probabilistic algorithms are also known for the same problem, see e.g. Angluin and Valiant (1979).

The limit behaviour of the fulfilment of the sufficient conditions in case of large random graphs is investigated experimentally. As a byproduct we started to investigate the fulfilment of the criteria in large Erdős-Rényi type random graphs G(n,p) when n tends to infinity. Our experiments have shown that the conditions are typically fulfilled if p>1/2, and they are typically violated if p<1/2. This finding is in accordance with the results by Pósa (1976) and Karp (see Chvátal, 1985).

This phenomenon is proved as a theorem. For the proof we used directed graphs to separate the edges so we can apply the central limit theorem for the degree distributions.

This study has been published in The Mathematica Journal, thus contains some useful modifications to increase the efficiency of the built in functions of Wolfram Mathematica.

Acknowledgement: The results descussed above are supported by the grant OTKA-108947.

3-Dimensional VLSI Routing – Results and Open Problems in Discrete Optimization

Attila Kiss (joint work with András Recski)

L. Eötvös University of Budapest

In the last millennium research in connection with VLSI routing has been modified a bit. Researchers, thanks to technological developments, started to develop 3-dimensional solutions for this problem. These challenges in electrical engineering lead mainly to problems in combinatorial optimization, like the simplified placement problem, the multisection problem or routing vertex disjoint Steiner-trees in a cubic grid.

I try to give a quick survey of these results highlighting those in the detailed routing phase, including some new results. At the end of my talk I would like to mention some open problems as well.

Acknowledgement: The results descussed above are supported by the grant OTKA-108947.

Graph-Bin Packing

Zsolt Tuza, Csilla Bujtás, György Dósa, Csanád Imreh, Judit Nagy-György

We study an optimization problem which is a common generalization of bin packing and graph embedding under distance constraints. A host graph H is given and the strorage capacity L (possibly infinite) of its vertices is also fixed. The input of the problem is a simple graph G with lower and upper bounds associated with its edges and weights on its vertices. We consider mappings f : V(G) → V(H) such that for each vertex x of H the total weight of vertices mapped to x does not exceed L, and if uv is an edge in G then the distance of f(u) and f(v) in H is between the lower and upper bounds specified for uv. The objective is to optimize f with respect to a given function, for instance to minimize the maximum distance between the images of vertices. Special cases of Graph-Bin Packing include many famous optimization problems. We study it from various aspects.

Extremal graph theory and algorithms

Miklós Simonovits

Rényi Institute, Budapest

Graph theory is strongly connected to algorithms, however, extremal graph theory is not the area where we primarily think of algorithms. Extremal graph theory primarily means that a "Universe" is fixed, like simple graphs, multigraphs, directed graphs, hypergraphs, and we try to optimize the number of edges under the condition that the graph does not have some fixed substructures. I will show that there are several areas in extremal graph theory, strongly connected to algorithms.

Waste wood recovery and reverse logistic

Aleksandar Todorović, Michael Burnard, Aleksandar Tošić,Andreja Kutnar, Andrej Brodnik

University of Primorska(http://carewood.eu/)

In this talk we will introduce a problem found in a wood science. The presented problem is one of work packages in H2020 CareWood (Cascading Recovered Wood). There are 17 partners from five EU countries participating in the project.

Used wood is nowadays most frequently used as a fuel. However the fact is that most of the wood can be reused. The remaining work packages are studying various aspects of used wood re-fabrication, while the work package we are describing is concerned with the efficient recovery of used wood. In contrast to logistic that is concerned with an efficient delivery of products from the suppliers or factory to the user, in our case we are dealing with a reverse logistic. The reverse logistic deals with and efficient collecting of used material at the consumers and delivering them to the plant (supplier).

In our talk we will describe the problem, classical methods used for solving it and technological issues to speed up the solving process. In the later we are mostly interested in a possibility to use distributed cloud based system such as Hadoop.

The work is supported by a WoodWisdom-Net+ and Ministry of Education, Science and Sport of Republic of Slovenia.