- Marcin Anholcer: Majority colorings of digraphs
- János Balogh: Online bin packing with cardinality constraints resolved
- Bo Chen: Supplier Competition with Option Contracts for Discrete Blocks of Capacity
- Béla Csaba: Embedding graphs having Ore-degree at most five
- György Dósa: The tight asymptotic ratio of First Fit algorithm for cardinality constrained binpacking
- András Frank: Decreasingly-minimal optimization
- Dries Goossens: Conference scheduling: a personalized approach
- Nebojsa Gvozdenovic: Synchronized tactical planning of sales and delivery routes
- Péter Hajnal: Two gemoterical applications of the semi-random method
- Tibor Illés: Operational research model for crew scheduling and application
- Gabriel Istrate: On the heapability of partial orders
- Branko Kavsek: Development and evaluation of different models for predicting turist category from texts
- Tamás Kis: Scheduling with non-renewable resources
- Martine Labbé: Theoretical and computational comparisons of formulations for Stackelberg bimatrix games
- Moritz von Looz: Parallel Mesh (Re)Partitioning with Balanced k-means
- István Miklós: The swap Markov chain is rapidly mixing on the realizations of linearly bounded degree sequences
- Nysret Musliu: Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning
- Benedek Nagy: On 5'-3' Watson-Crick finite and pushdown automata
- Rolf Niedermeier: Fixed-Parameter Tractability inside P
- Csaba Raduly-Baka: Discrete structures in access road design
- Sándor Szabó: Cliques and differential equations
- Tamás Terlaky: On Disjuntive Conic Cuts for Mixed Integer Second Order Cone Optimization

e-mail: m.anholcer@ue.poznan.pl

e-mail: bosek@tcs.uj.edu.pl

e-mail: j.grytczuk@mini.pw.edu.pl

Majority coloring of a digraph is a coloring of its vertices such that for each vertex v, at least half of the out-neighbors of v have different colors than v. A digraph D is majority k–choosable if for any assignment of lists of colors of size k to the vertices there is a majority coloring of D from these lists. We present an algorithm that generates a majority coloring of arbitrary digraph from lists of size 4. In fact, our method solves a more general problem, where the fraction of out-neighbors having same color may be different for every vertex (in particular, not necessarily equal to 1/2). In addition, we also prove some results on the majority colorings of infinite digraphs.

**Keywords:** majority coloring, unfriendly partition, majority k-choosability, digraph, infinite digraph.

**AMS Subject Classification:** 05C15, 05C20, 05C63.

Cardinality constrained bin packing or bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k≥2, items having sizes in (0,1] associated with them are presented one by one to be packed into unit capacity bins, such that the capacities of bins are not exceeded, and no bin receives more than k items. We resolve the online problem in the sense that we prove a lower bound of 2 on the overall asymptotic competitive ratio. This closes the long standing open problem of finding the value of the best possible overall asymptotic competitive ratio, since an algorithm of an absolute competitive ratio 2 for any fixed value of k is known. Additionally, we significantly improve the known lower bounds on the asymptotic competitive ratio for every specific value of k. The novelty of our constructions is based on full adaptivity that creates large gaps between item sizes. Thus, our lower bound inputs do not follow the common practice for online bin packing problems of having a known in advance input consisting of batches for which the algorithm needs to be competitive on every prefix of the input. Last, we show a lower bound strictly larger than 2 on the asymptotic competitive ratio of the online 2-dimensional vector packing problem, and thus provide for the first time a lower bound larger than 2 on the asymptotic competitive ratio for the vector packing problem in any fixed dimension.

When a firm faces an uncertain demand, it is common to procure supply using some type of option in addition to spot purchases. A typical problem of this type involves capacity being purchased in advance, with a separate paymentmade that applies only to the part of the capacity that is needed. We consider a discrete version of this problem in which competing suppliers choose a reservation price and an execution price for blocks of capacity, and the buyer, facing known distributions of demand and spot price, needs to decide which blocks to reserve. We show how to solve the buyer's combinatorial problem efficiently and prove that suppliers can do no better than offer blocks at execution prices that match their costs, making profits only from the reservation part of their bids. Finally, we show that in an equilibriumthe buyer selects thewelfare maximizing set of blocks.

Joint work with Edward Anderson (University of Sydney, Australia) and Lusheng Shao (University of Melbourne, Australia)

Let H and G be simple graphs on n vertices, where n is sufficiently large. Define the Ore-degree of an edge as the sum of the degrees of its endpoints. Then we define the Ore-degree of H as the maximum of the Ore-degrees taken on the edges of H. We prove that if H has Ore-degree at most 5 and G has minimum degree at least 2n/3 then H is a spanning subgraph of G.

In bin packing with cardinality constraints (BPCC), there is an upper bound k on the number of items that can be packed into each bin, additionally to the standard constraint on the total size of items packed into a bin. We study the algorithm First Fit, that acts on a list of items, packing each item into the minimum indexed bin that contains at most k-1 items and has sufficient space for the item.

An upper bound, namely 2.7-2.4/k for the asymptotic approximation ratio of FF was known from 1975. Now we give the tight bound for any specific value of k.

This is as follows: 5/2- 2/k for k is between 2 and 4; 8/3-8/(3k) if k is between 4 and 10, and 2.7-3/k if k is at least 10 (where the values 4 and 10 are included in two cases each). For the tightness proof we use different weighting functions for the different cases.

In a digraph we want to find K spanning arborescences such the most used edge belongs to a minimum number of arborescences, subject to this, the second most used edge belongs to a minimum number of arborescences, and so on. For short, we are interested in a decreasingly-minimal packing of K arborescences. In an analogous problem, we look for a decreasingly-minimal strongly connected orientation of a graph, that is, the largest in-degree of a node should be as small as possible, subject to this, the second largest in-degree should be as small as possible, and so on.

Similar questions can be posed concerning many other known combinatorial optimization problems such as packing st-paths of a digraph or bases of a matroid. In the literature, this kind of problems are sometimes called ”egalitarian” or ”shifted” or ”fair” optimization. When K is small, a straightforward parallel edge- multiplicating technique reduces the problem to the minimum cost version of the basic problem. However, for large K this approach is hopeless to get a polynomial algorithm. In this talk, we develop a strongly polynomial algorithm, for network flows and polymatroid intersections.

The talk is based on a joint work with Kazuo Murota.

Scientific conferences have become an essential part of academic research and require significant investments (e.g. time and money) from their participants. It falls upon the organizers to develop a schedule that allows the participants to attend the talks of their interest. We present a combined approach of assigning talks to rooms and time slots, grouping talks into sessions, and deciding on an optimal itinerary for each participant. Our goal is to maximize attendance, taking into account the common practice of session hopping. On a secondary level, we accommodate presenters' availabilities. We use a hierarchical optimization approach, sequentially solving integer programming models, which has been applied to construct the schedule of the MathSport International (2013), MAPSP (2015) and ORBEL (2017) conferences.

illes@math.bme.hu, musz.sunil@gmail.com

Today resource scheduling problems are in the spotlight of operations research, as these problems have several applications in real life as well. These problems can be considered as assignment problems with additional requirements. Application areas cover the scheduling of pilots and stewardess to designated flights, shop assistants to shifts and public transport (vehicles) to routes, and many more similar type of problems. The additional requirements are greatly dependent on the application, blemishing the flow network behaviour of the problem, hence the characterisation of these problems can only be achieved by integer programming, usually leading to an NP-hard problem. Therefore the solution of these optimization models in practice is a real professional challenge.

Our talk focuses on scheduling bus drivers for different lines of the public transport network of Budapest. Although the actual transport routes and timetables are rarely modified, it is essential to constantly develop improved schedules, which is still surprisingly done in Excel for the Budapest Transportation Company. On the one hand this practise from the company side requires a huge amount of time and human resources. On the other hand the quality of the solution is either not guaranteed or not known. (Usually, both is true.)

In our approach, the initial step was to build the basic integer linear programming (ILP) model that includes all constraints possed by the client. The obtained ILP model falls into the NP-hard problem class. Since there is no polynomial algorithm for such problems, the main aim was to develop a model variant that can be solved by available software effciently giving an acceptable result for even larger problem instances within a reasonable time frame.

We show that using a combination of an aggregate model and a more detailed one, we could effciently get such solutions that are usually better quality of that one produced by the expert of the transportation company and in most of the cases the result could be obtained using much less time. In our approach we are not following the frequently used column generation technique based on drivers feasible rosters.

The work was carried out in collaboration with T-Systems Hungary Ltd.

In recent years the field of text mining has witnessed an exponential growth due to rapid technological development and ubiquitous information technology. When discovering useful information from natural languages, classification algorithms are combined with the analysis of lexicographic and linguistic patterns. The main objective of the paper/talk is to briefly present the field of text mining including all relevant methodologies and techniques. Moreover, we developed and evaluated various predictive models based on the case study of the Slovenian Tourist Corpus which encompasses the learning set of 4.688 texts. These texts have been previously classified in one of the 27 classes by an expert. We compared the performance of different machine learning algorithms for classification on the original and lemmatized texts that were properly pre-processed before the modelling process. We examined the effect of eliminating stop words and those without any information gain on the final model accuracy. Open source software WEKA was used, which includes a wide collection of techniques and algorithms for the construction and evaluation of predictive models. The final evaluation confirms the minimal impact of the factors that were expected to affect the accuracy of the predictive models.

kis.tamas@sztaki.mta.hu

In the talk I give an overview of the published results on the subject in the title, and then I present new, yet unpublished results on machine scheduling problems with additional non-renewable resources and the total weighted completion time objective. I will discuss complexity and approximability results, and we will also see that well-known scheduling rules prove once more useful in a new context.

Stackelberg Games confront contenders, a leader and a follower, with opposed objectives, each wanting to optimize their rewards. The objective of the game is for the leader to commit to a reward-maximizing strategy anticipating that the follower will best respond.

A Stackelberg game can be modelled as a bilevel bilinear optimization problem. We present different single level reformulations and compare their LP relaxations from both theoretical and computational points of view.

Let D = {d_{1,1}, d_{1,2}, . . . , d_{1,n}}, {d_{2,1}, d_{2,2}, . . . , d_{2,m}} be a degree sequence
of a bipartite graph. The swap Markov chain takes two random
edges, (v_{1}, u_{1}),(v_{2}, u_{2}), of a relization G of D, removes it and adds edges
(v_{1}, u_{2}) and (v_{2}, u_{1}) if none of them are presented in G. It is well known
that such a Markov chain is irreducible on the realizations of D. The conjecture
is that it is rapidly mixing, however, the rapid mixing has been proved only for very limited degree sequences so far. Here we prove the following theorem.

Let 0 ≤ c_{1} ≤ c_{2} ≤ |U| = n and
0 ≤ d_{1} ≤ d_{2} ≤ |V | = m be integer
parameters and assume that D satisfies the following properties:

c_{1} ≤ d(v) ≤ c_{2}, ∀v ∈ V

d_{1} ≤ d(u) ≤ d_{2}, ∀u ∈ U.

Furthermore, assume that c_{2} ≤ c_{1} + 1 or d_{2} ≤ d_{1} + 1 or

(c_{2} − c_{1} − 1) · (d_{2} − d_{1} − 1) < 1 + max {c_{1}(m − d_{2}), d_{1}(n − c_{2})}

holds. Then the swap Markov chain on the realizations of this bipartite degree sequence is rapidly mixing.

The prescribed conditions allow to prove rapid mixing for a much wider class of degree sequences. For example, our theorem covers the case when n = m, and all degrees are between 1/3 n and 2/3 n, inclusive.

Dynamic Programming (DP) over tree decompositions is a well-established method to solve problems - that are in general NP-hard - efficiently for instances of small treewidth. Experience shows that (i) heuristically computing a tree decomposition has negligible runtime compared to the DP step; and (ii) DP algorithms exhibit a high variance in runtime when using different tree decompositions; in fact, given an instance of the problem at hand, even decompositions of the same width might yield extremely diverging runtimes. We propose a general method that is based on selection of the best decomposition from an available pool of heuristically generated ones. For this purpose, we require machine learning techniques that provide automated selection based on features of the decomposition rather than on the actual problem instance. Thus, one main contribution of this work is to propose novel features for tree decompositions. Moreover, we report on extensive experiments in different problem domains which show a significant speedup when choosing the tree decomposition according to this concept over simply using an arbitrary one of the same width.

Based on joint work with Michael Abseher and Stefan Woltran

Watson-Crick automata are inspired from the Nature, as instead of a normal tape, a Watson-Crick tape, i.e., a DNA molecule is considered as input. A DNA molecule has two strands, subsequently Watson-Crick automata have two reading heads, one for each strand. DNA strands have orientation, the 5'->3' direction is preferred in some biochemical reactions. In 5'->3' Watson-Crick automata the two reading heads start from the two extremes of the input (the opposite ends of the molecule) and finish the process when the heads meet. With 5'->3' Watson-Crick finite automata the class of linear context-free languages can be accepted, and some of its subclasses by some restricted variants. Extending these automata with a pushdown stack, a new mildly context-sensitive family of languages can be accepted containing all the context-free languages, and the linguistically important three non context-free languages. Variants of this model will also be shown.

We discuss and survey some recent developments concerning the application of concepts of parameterized algorithmics to polynomial-time solvable problems. Example problems include Matching, Triangle Detection and Enumeration, and Graph Hyperbolicity.

We consider the problem of designing an road network in a forest with the goal of providing access to tree harvest locations. The environment is modelled as a node induced grid graph, with each node (cell) containing properties of the respective area. A number of objectives can be considered when designing road networks: topology, environmental restrictions, access to specific areas and soil properties. Current solution in forest access road design focus on finding optimal routes to pre-specified locations with the goal of minimising distance. These are often modelled using Steiner trees. Although Steiner trees provide a theoretical optimum solution, they are both hard to find, and not practical in larger areas. In practice, access road networks are often end up as sets of loops, to improve traffic and avoid congestion. We propose a new model using cactus-like graph structures. Our goal is to find a minimum cost cactus-like subgraph, subject to a prize limit (amount of accessed harvestable sites). We propose hybrid heuristic methods to solve the problem.

In the talk we describe how approximate numerical solutions of a suitable initial value problem of a system of ordinary differential equations can be used to establish rigorous lower and upper estimate for the clique number of a given graph.

In order to assess the practical utility of the proposed approach we have carried out numerical experiments. We outline the benchmark instances used in the computations and also present tables summarising the results.

Lehigh University, Bethlehem, PA, USA

The recently developed Disjunctive Conic Cuts (DCCs) for Mixed Integer Second Order Cone Optimization (MISOCO) problems have gained significant interest in the optimization community. After introducing DCCs, we shortly discuss and demonstrate the power of DCCs in solving MISOCO problems. Finally we discuss the identification of cases when the disjunctions are pathological, i.e., the convex hall of the disjunctive set coincides with the original set. Such cases include the MISOCO representation of mixed integer p-order cone optimization problems.

Joint work with: Julio Góez, NHH, Norway, Mohammad Shahabsafa, ISE ,Lehigh University