@inproceedings{SagnolBlancoSauvage, author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibaut}, title = {Approximation Hierarchies for the cone of flow matrices}, series = {INOC 2017 - 8th International Network Optimization Conference}, volume = {64}, booktitle = {INOC 2017 - 8th International Network Optimization Conference}, doi = {10.1016/j.endm.2018.02.002}, pages = {275 -- 284}, abstract = {Let \$G\$ be a directed acyclic graph with \$n\$ arcs, a source \$s\$ and a sink \$t\$. We introduce the cone \$K\$ of flow matrices, which is a polyhedral cone generated by the matrices \$1_P 1_P^T \in R^{n\times n}\$, where \$1_P\in R^n\$ is the incidence vector of the \$(s,t)\$-path \$P\$. Several combinatorial problems reduce to a linear optimization problem over \$K\$. This cone is intractable, but we provide two convergent approximation hierarchies, one of them based on a completely positive representation of \$K\$. We illustrate this approach by computing bounds for a maximum flow problem with pairwise arc-capacities.}, language = {en} } @inproceedings{SagnolSchmidtgenanntWaldschmidtTesch, author = {Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel and Tesch, Alexander}, title = {The Price of Fixed Assignments in Stochastic Extensible Bin Packing}, series = {WAOA 2018: Approximation and Online Algorithms}, volume = {11312}, booktitle = {WAOA 2018: Approximation and Online Algorithms}, doi = {10.1007/978-3-030-04693-4_20}, pages = {327 -- 347}, abstract = {We consider the stochastic extensible bin packing problem (SEBP) in which n items of stochastic size are packed into m bins of unit capacity. In contrast to the classical bin packing problem, the number of bins is fixed and they can be extended at extra cost. This problem plays an important role in stochastic environments such as in surgery scheduling: Patients must be assigned to operating rooms beforehand, such that the regular capacity is fully utilized while the amount of overtime is as small as possible. This paper focuses on essential ratios between different classes of policies: First, we consider the price of non-splittability, in which we compare the optimal non-anticipatory policy against the optimal fractional assignment policy. We show that this ratio has a tight upper bound of 2. Moreover, we develop an analysis of a fixed assignment variant of the LEPT rule yielding a tight approximation ratio of (1+e-1)≈1.368 under a reasonable assumption on the distributions of job durations. Furthermore, we prove that the price of fixed assignments, related to the benefit of adaptivity, which describes the loss when restricting to fixed assignment policies, is within the same factor. This shows that in some sense, LEPT is the best fixed assignment policy we can hope for.}, language = {en} }