# Timişoara-Szeged Theory Seminar

## Timişoara-Szeged Theory Seminar (First edition)

When: November 26, 2015. Tentatively 10:30 am. Room 223.

Where: Department of Computer Science, West University of Timişoara, Romania.

Agenda: 6 talks, roughly 30 minutes each.

Tentative Schedule

Morning session: 11:00-12:30

1. József Békesi (Szeged):

[-]
[+]

(Joint work with Dino Ahr, Gábor Galambos, Michael Jung , Marcus Oswald and Gerhard Reinelt)

The coupled-task problem is to schedule n jobs on one machine where each job consists of two subtasks with required exact delay time between them. The objective is to minimize the makespan, i.e. the finishing time of the last job. This problem was analyzed in depth by Orman and Potts. They investigated the complexity of different cases depending on the lengths $a_i$ and $b_i$ of the two subtasks and the delay time $L_i$. NP-hardness proofs or polynomial algorithms were given for several cases.

The next figure presents a possible schedule.

In this talk we present some results we achieved in the last years. We investigated some special cases of the general problem.
First we present an algorithm for the so called identical case, where the 3 parameters of the jobs are identical, i.e. $a_i=a, b_i=b, L_i=L$ for all i. The complexity of this subproblem is an open question.
Next we present an improved analysis of an approximation algorithm given by Ageev and Baburin for an NP-hard special case when $a_i=b_i=1$.
Finally we present a branch and bound method for the general problem.

[1] D. Ahr, J. Bekesi, G. Galambos, M. Oswald, G. Reinelt: An Exact Algorithm for Scheduling Identical Coupled Task Problems, Mathematical Methods of Operations Research, 59(2), 2004.
[2] J. Békési, G. Galambos, M. Oswald, G. Reinelt , Improved Analysis of an Algorithm for the Coupled Task Problem with UET Jobs, Operations Research Letters 37, 2009, 93-96
[3] J. Békési, G. Galambos, M. N. Jung, M. Oswald, G. Reinelt, A branch-and-bound algorithm for the coupled task problem, Mathematical Methods of Operations Research 80, 2014, 47-81.

2. Cosmin Bonchiş (Timişoara):
[-]
[+]

Partition into heapable sequences, heap tableaux and a multiset version of Hammersley’s process.

(Joint work with Gabriel Istrate)

A sequence of integers is called heapable (Byers et al. [1]) if it can be successively inserted into a binary tree respecting the min heap property so that every number is inserted at a leaf.

We investigate partitioning of integer sequences into heapable
subsequences. We show that an extension of patience sorting computes the
decomposition into a minimal number of heapable subsequences (MHS).
We connect this parameter to an interactive particle system, a multiset
extension of Hammersley’s process, and investigate its expected value
on a random permutation. In contrast with the (well studied) case of the
longest increasing subsequence, we bring experimental evidence that the
correct asymptotic scaling is

$E[MinHeap[\pi]\sim \frac{1+\sqrt{5}}{2}\cdot \ln(n)$

Finally we give a heap-based extension of Young tableaux, prove a hook inequality and an extension of the Robinson-Schensted correspondence.

[1] Byers, John, et al. Heapable sequences and subseqeuences. Proceedings of ANALCO (2011): 33-44.
[2] G. Istrate, C. Bonchis. Partition into heapable sequences, heap tableaux and an explosive version of the Hammersley process. Proceedings of CPM’2015.

3. János Balogh(Szeged):

[-]
[+]

Some results of online and semi-online bin packing

Joint work with József Békési, Gábor Galambos, and Gerhard Reinelt)

In the talk we present some results we achieved in the last years in the field of online and semi-online bin packing.

Bin packing (BP) is a classical combinatorial problem. In the classical BP problem items of a list are appeared and the algorithm has to pack the items into unit capacity bins. The size of an item is in the (0,1] interval, each bin has size is 1, and the total size of the items in a bin is at most one.
In the online version of BP (online bin packing, OBP) the items are revealed one by one and the algorithm has to decide the place (bin) of the current item without any information of the remaining items.
If ALG is the number of bins used by an algorithm, and OPT is the number of bins of an optimal one, then we say that the algorithm is (asymptotically) C-competitive if OPT(L)<=C ALG(L) + K holds for each L input list, where C is at least one, and K>=0 is a constant independent from the input.
If the same holds with K=0 then we say the algorithm is absolute C-competitive.
In [1] we gave a 1.54037 lower bound for OBP, improving a 20-year-old result of van Vliet.

Semi-on-line bin packing is an intermediate model between offline and online bin pan packing, where the online bin packing algorithm has some extra information, or some extra operations are allowed for it (e.g. restricted repacking of bounded number of previously packed items).

Regarding the asymptotic competitive ratio, for the case of OBP with restricted repacking we prove a lower bound of 1.3871 in [3], while in [4] we proved some upper bounds for the same problem.
For the case of online bin packing where the input is given in non-increasing order we showed an asymptotic lower bound of 54/47 in [1].
We dealt with another semi-online BP problem in [4], where the value of OPT is known in advance for the OBP algorithm. We gave a 1.3231 (asymptotic) lower bound for this case.

[1] Balogh, J., J. Békési, and G. Galambos, New lower bounds for certain classes of bin packing algorithms, Theoretical Computer Science, 440-441 (2012), 1-13;
[2] Balogh, J., J. Békési, G. Galambos, and G. Reinelt, Lower bound for the online bin packing problem with restricted repacking, SIAM Journal on Computing, 38(2008), 398-410.
[3] Balogh, J., J. Békési, G. Galambos, and G. Reinelt, On-line bin packing with restricted repacking, Journal of Combinatorial Optimization, 27(1), 115-131, 2014.
[4] Balogh, J. and J. Békési, Semi-on-line bin packing: a short overview and a new lower bound, Central European Journal of Operations Research, 21(4), 685-698, 2013.

Afternoon Session: 2:15-4:00

1. Mircea Marin (Timişoara):
[-]
[+]

Factorization of regular tree languages. Algorithms and applications.

Regular hedge languages are an extension of regular tree languages that received renewed attention since their recognition as a formal model of XML schemata. They share several properties with regular languages, but their study is more involved because we need to analyze regularities of sequences of trees instead of words. We show that one shared property is the existence of only finitely many language factors and the possibility to compute and arrange them in a factor matrix with some remarkable properties. We outline an algorithm for the computation of the factor matrix and indicate an application of the factor matrix of an RHL to the solution of a concrete language reconstruction problem.

[1] J. H. Conway, Regular Algebra and Finite Machines, ser. Mathematics series. Chapman and Hall, 1971.
[2] H. Hosoya, J. Vouillon, and B. C. Pierce, Regular expression types for XML, ACM Transactions on Programming
Languages and Systems, vol. 27, no. 1, pp. 46?90, 2005.
[3] M. Marin and T. Kutsia, Linear systems for regular hedge languages, in Advances in Databases and Information Systems. ADBIS 2009.
ser. LNCS: Springer, 2010.
[4] M. Marin, A. Craciun, Factorizations of Regular Hedge Languages. SYNASC 2009, Proceedings, pp. 307-314, 2009.
[5] M. Marin, T. Kutsia. On the computation of quotients and factors of regular languages. Frontiers of Computer Science in China 4(2): 173-184, 2010.

2. Miklós Krész (Szeged):
[-]
[+]

Maximally-matchable edges, decomposition theory and constraint satisfaction problems

In matching theory it is a basic problem to determine all the edges in a given graph which can be extended to a maximum matching. Such edges are called maximally matchable or allowed edges. Apart from the graph theory community (see e.g [1]), researchers in constraint programming have also investigated this problem (cf. [2-4]). The motivation for studying the question from constraint programming point of view is originating from certain constraint propagation methods ([3]). In this talk first we will review the methods from the literature for determining the maximally-matchable edges. Then a decomposition theory based on the matching structure is presented with showing the related algorithmic concept for identifying the allowed edges. It will be also shown that the complexity of the new method can be expressed with the help of a graph parameter arising from the developed decomposition structure.

[1] M. de Carvalho, J. Cheriyan, An O(VE) algorithm for ear decompositions of matching-covered graphs, Proc. ACM/SIAM Symposium on Discrete Algorithms (SODA), pp.415–423.
[2] R. Cymer: Gallai-Edmonds Decomposition as a Pruning Technique. CEJOR (2015) 23: 149-185.
[3] J.C. Regin: The Symmetric Alldiff Constraint. IJCAI 1999: 420-425.
[4] S. Thiel: Efficient Algorithms for Constraint Propagation and for Processing Tree Drescriptions. PhD Thesis, Universitat des Saarlandes, 2004.

3. Gabriel Istrate (Timişoara):
[-]
[+]

The minimum entropy submodular set cover problem.

(Joint work with Cosmin Bonchis).

We study minimum entropy submodular set cover, a variant of the submodular set cover problem (Wolsey [1], Fujito [2], etc) that generalizes the minimum entropy set cover problem (Halperin and Karp [3], Cardinal et al.[4])

We give a general bound of the approximation performance of the greedy algorithm using an approach that can be interpreted in terms of a particular type of biased network flows. As an application we rederive known results for the Minimum Entropy Set Cover and Minimum Entropy Orientation problems, and obtain a nontrivial bound for a new problem called the Minimum Entropy Spanning Tree problem.

The problem can be applied to (and is partly motivated by) the definition of worst-case approaches to fairness in concave cooperative games, similar to the notion of price of anarchy in noncooperative settings. I will also discuss connections to other problems in the literature.

[1] Wolsey, Laurence A. “An analysis of the greedy algorithm for the submodular set covering problem.” Combinatorica 2.4 (1982): 385-393.
[2] Fujito, Toshihiro. “Approximation algorithms for submodular set cover with applications.” IEICE Transactions on Information and Systems 83.3 (2000): 480-487.
[3] Halperin, Eran, and Richard M. Karp. “The minimum-entropy set cover problem.” Theoretical computer science 348.2 (2005): 240-250.
[4] Cardinal, Jean, Samuel Fiorini, and Gwenaël Joret. “Tight results on minimum entropy set cover.” Algorithmica 51.1 (2008): 49-60.

4. Open discussion.