8 Search Results for "Klein, Kim-Manuel"

Document
DOI: 10.4230/LIPIcs.MFCS.2021.39
Fuzzy Simultaneous Congruences

Authors: Max A. Deppert, Klaus Jansen, and Kim-Manuel Klein

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We introduce a very natural generalization of the well-known problem of simultaneous congruences. Instead of searching for a positive integer s that is specified by n fixed remainders modulo integer divisors a₁,… ,a_n we consider remainder intervals R₁,… ,R_n such that s is feasible if and only if s is congruent to r_i modulo a_i for some remainder r_i in interval R_i for all i. This problem is a special case of a 2-stage integer program with only two variables per constraint which is is closely related to directed Diophantine approximation as well as the mixing set problem. We give a hardness result showing that the problem is NP-hard in general. By investigating the case of harmonic divisors, i.e. a_{i+1}/a_i is an integer for all i < n, which was heavily studied for the mixing set problem as well, we also answer a recent algorithmic question from the field of real-time systems. We present an algorithm to decide the feasibility of an instance in time 𝒪(n²) and we show that if it exists even the smallest feasible solution can be computed in strongly polynomial time 𝒪(n³).
Cite as

Max A. Deppert, Klaus Jansen, and Kim-Manuel Klein. Fuzzy Simultaneous Congruences. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{deppert_et_al:LIPIcs.MFCS.2021.39,
  author =	{Deppert, Max A. and Jansen, Klaus and Klein, Kim-Manuel},
  title =	{{Fuzzy Simultaneous Congruences}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.39},
  URN =		{urn:nbn:de:0030-drops-144792},
  doi =		{10.4230/LIPIcs.MFCS.2021.39},
  annote =	{Keywords: Simultaneous congruences, Integer programming, Mixing Set, Real-time scheduling, Diophantine approximation}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.23
An Experimental Study of External Memory Algorithms for Connected Components

Authors: Gerth Stølting Brodal, Rolf Fagerberg, David Hammer, Ulrich Meyer, Manuel Penschuck, and Hung Tran

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
We empirically investigate algorithms for solving Connected Components in the external memory model. In particular, we study whether the randomized O(Sort(E)) algorithm by Karger, Klein, and Tarjan can be implemented to compete with practically promising and simpler algorithms having only slightly worse theoretical cost, namely Borůvka’s algorithm and the algorithm by Sibeyn and collaborators. For all algorithms, we develop and test a number of tuning options. Our experiments are executed on a large set of different graph classes including random graphs, grids, geometric graphs, and hyperbolic graphs. Among our findings are: The Sibeyn algorithm is a very strong contender due to its simplicity and due to an added degree of freedom in its internal workings when used in the Connected Components setting. With the right tunings, the Karger-Klein-Tarjan algorithm can be implemented to be competitive in many cases. Higher graph density seems to benefit Karger-Klein-Tarjan relative to Sibeyn. Borůvka’s algorithm is not competitive with the two others.
Cite as

Gerth Stølting Brodal, Rolf Fagerberg, David Hammer, Ulrich Meyer, Manuel Penschuck, and Hung Tran. An Experimental Study of External Memory Algorithms for Connected Components. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 23:1-23:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{brodal_et_al:LIPIcs.SEA.2021.23,
  author =	{Brodal, Gerth St{\o}lting and Fagerberg, Rolf and Hammer, David and Meyer, Ulrich and Penschuck, Manuel and Tran, Hung},
  title =	{{An Experimental Study of External Memory Algorithms for Connected Components}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{23:1--23:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.23},
  URN =		{urn:nbn:de:0030-drops-137958},
  doi =		{10.4230/LIPIcs.SEA.2021.23},
  annote =	{Keywords: Connected Components, Experimental Evaluation, External Memory, Graph Algorithms, Randomization}
}
Document
DOI: 10.4230/OASIcs.iPMVM.2020.16
Physical Modeling of Process Forces in Grinding

Authors: Praveen Sridhar, Daniel Mannherz, Raphael Bilz, Kristin M. de Payrebrune, Mahesh R.G. Prasad, and Juan Manuel Rodríguez Prieto

Published in: OASIcs, Volume 89, 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020)

Abstract
This paper deals with material removal mechanisms in grinding by considering single grit-workpiece interactions. Individual investigations were performed both experimentally and using finite element simulations. Firstly, a comparison between the Johnson-Cooke material model and a Crystal Plasticity finite element method was performed with the help of micro-indentation experiments. Here the research question was answered if an anisotropic material model better describe the grinding process and process forces compared to an isotropic material model. Secondly, four discretization approaches were employed: pure Lagrangian (LAG), Arbitrary Lagrange Eulerian (ALE), Particle Finite Element Method (PFEM), and Smooth Particle Hydrodynamics (SPH), to simulate a micro-cutting operation of A2024 T351 aluminium. This study aims to compare the conventional approaches (LAG and ALE) to newer approaches (PFEM and SPH). The orthogonal cutting models were benchmarked against a micro-cutting experiment presented in literature, by comparing the obtained cutting and passive forces. The study was then extended to negative rake angles to study the effect on the discretization approaches for grinding. Thirdly, scratch experiments were investigated for a brittle material sodalime glass and A2024 T351 aluminium. Effects of the linear speed of the device, depth of cut, and conical tool angle were analyzed and tendencies are built. Finally, a realistic simulation of the manufacturing process of a grinding wheel was developed, starting with the raw material, compression, sintering, and dressing until the final grinding surface. As a result of the simulations, virtual grinding wheel topographies can be visualized and analyzed with regard to the output variables from grinding wheels such as bonding strength and static grain count. The individual research studies help in understanding the material removal mechanisms in a single grit scratch process as well as in the understanding of the overall grinding wheel topography. This in turn helps in the developing an overall physical force model for scratching/grinding to predict mechanical output parameters and hence reduce the need for experimentation.
Cite as

Praveen Sridhar, Daniel Mannherz, Raphael Bilz, Kristin M. de Payrebrune, Mahesh R.G. Prasad, and Juan Manuel Rodríguez Prieto. Physical Modeling of Process Forces in Grinding. In 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020). Open Access Series in Informatics (OASIcs), Volume 89, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sridhar_et_al:OASIcs.iPMVM.2020.16,
  author =	{Sridhar, Praveen and Mannherz, Daniel and Bilz, Raphael and de Payrebrune, Kristin M. and Prasad, Mahesh R.G. and Prieto, Juan Manuel Rodr{\'\i}guez},
  title =	{{Physical Modeling of Process Forces in Grinding}},
  booktitle =	{2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020)},
  pages =	{16:1--16:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-183-2},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{89},
  editor =	{Garth, Christoph and Aurich, Jan C. and Linke, Barbara and M\"{u}ller, Ralf and Ravani, Bahram and Weber, Gunther H. and Kirsch, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.iPMVM.2020.16},
  URN =		{urn:nbn:de:0030-drops-137651},
  doi =		{10.4230/OASIcs.iPMVM.2020.16},
  annote =	{Keywords: grinding, single grit approach, finite element method, smooth particle hydrodynamics, particle finite element method, scratch experiments, virtual grinding wheel model}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.44
Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times

Authors: Klaus Jansen, Kim-Manuel Klein, Marten Maack, and Malin Rau

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
Integer linear programs of configurations, or configuration IPs, are a classical tool in the design of algorithms for scheduling and packing problems, where a set of items has to be placed in multiple target locations. Herein a configuration describes a possible placement on one of the target locations, and the IP is used to chose suitable configurations covering the items. We give an augmented IP formulation, which we call the module configuration IP. It can be described within the framework of n-fold integer programming and therefore be solved efficiently. As an application, we consider scheduling problems with setup times, in which a set of jobs has to be scheduled on a set of identical machines, with the objective of minimizing the makespan. For instance, we investigate the case that jobs can be split and scheduled on multiple machines. However, before a part of a job can be processed an uninterrupted setup depending on the job has to be paid. For both of the variants that jobs can be executed in parallel or not, we obtain an efficient polynomial time approximation scheme (EPTAS) of running time f(1/epsilon) x poly(|I|) with a single exponential term in f for the first and a double exponential one for the second case. Previously, only constant factor approximations of 5/3 and 4/3 + epsilon respectively were known. Furthermore, we present an EPTAS for a problem where classes of (non-splittable) jobs are given, and a setup has to be paid for each class of jobs being executed on one machine.
Cite as

Klaus Jansen, Kim-Manuel Klein, Marten Maack, and Malin Rau. Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ITCS.2019.44,
  author =	{Jansen, Klaus and Klein, Kim-Manuel and Maack, Marten and Rau, Malin},
  title =	{{Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.44},
  URN =		{urn:nbn:de:0030-drops-101375},
  doi =		{10.4230/LIPIcs.ITCS.2019.44},
  annote =	{Keywords: Parallel Machines, Setup Time, EPTAS, n-fold integer programming}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.49
Faster Algorithms for Integer Programs with Block Structure

Authors: Friedrich Eisenbrand, Christoph Hunkenschröder, and Kim-Manuel Klein

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider integer programming problems max {c^Tx : A x = b, l <= x <= u, x in Z^{nt}} where A has a (recursive) block-structure generalizing n-fold integer programs which recently received considerable attention in the literature. An n-fold IP is an integer program where A consists of n repetitions of submatrices A in Z^{r × t} on the top horizontal part and n repetitions of a matrix B in Z^{s × t} on the diagonal below the top part. Instead of allowing only two types of block matrices, one for the horizontal line and one for the diagonal, we generalize the n-fold setting to allow for arbitrary matrices in every block. We show that such an integer program can be solved in time n^2t^2 phi x (r s delta)^{O(rs^2+ sr^2)} (ignoring logarithmic factors). Here delta is an upper bound on the largest absolute value of an entry of A and phi is the largest binary encoding length of a coefficient of c. This improves upon the previously best algorithm of Hemmecke, Onn and Romanchuk that runs in time n^3t^3 phi x delta^{O(st(r+t))}. In particular, our algorithm is not exponential in the number t of columns of A and B. Our algorithm is based on a new upper bound on the l_1-norm of an element of the Graver basis of an integer matrix and on a proximity bound between the LP and IP optimal solutions tailored for IPs with block structure. These new bounds rely on the Steinitz Lemma. Furthermore, we extend our techniques to the recently introduced tree-fold IPs, where we again present a more efficient algorithm in a generalized setting.
Cite as

Friedrich Eisenbrand, Christoph Hunkenschröder, and Kim-Manuel Klein. Faster Algorithms for Integer Programs with Block Structure. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{eisenbrand_et_al:LIPIcs.ICALP.2018.49,
  author =	{Eisenbrand, Friedrich and Hunkenschr\"{o}der, Christoph and Klein, Kim-Manuel},
  title =	{{Faster Algorithms for Integer Programs with Block Structure}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{49:1--49:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.49},
  URN =		{urn:nbn:de:0030-drops-90537},
  doi =		{10.4230/LIPIcs.ICALP.2018.49},
  annote =	{Keywords: n-fold, Tree-fold, Integer Programming}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.13
Online Strip Packing with Polynomial Migration

Authors: Klaus Jansen, Kim-Manuel Klein, Maria Kosche, and Leon Ladewig

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
We consider the relaxed online strip packing problem, where rectangular items arrive online and have to be packed into a strip of fixed width such that the packing height is minimized. Thereby, repacking of previously packed items is allowed. The amount of repacking is measured by the migration factor, defined as the total size of repacked items divided by the size of the arriving item. First, we show that no algorithm with constant migration factor can produce solutions with asymptotic ratio better than 4/3. Against this background, we allow amortized migration, i.e. to save migration for a later time step. As a main result, we present an AFPTAS with asymptotic ratio 1 + O(epsilon) for any epsilon > 0 and amortized migration factor polynomial in 1/epsilon. To our best knowledge, this is the first algorithm for online strip packing considered in a repacking model.
Cite as

Klaus Jansen, Kim-Manuel Klein, Maria Kosche, and Leon Ladewig. Online Strip Packing with Polynomial Migration. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2017.13,
  author =	{Jansen, Klaus and Klein, Kim-Manuel and Kosche, Maria and Ladewig, Leon},
  title =	{{Online Strip Packing with Polynomial Migration}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.13},
  URN =		{urn:nbn:de:0030-drops-75620},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.13},
  annote =	{Keywords: strip packing, bin packing, online algorithms, migration factor}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.72
Closing the Gap for Makespan Scheduling via Sparsification Techniques

Authors: Klaus Jansen, Kim-Manuel Klein, and José Verschae

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Makespan scheduling on identical machines is one of the most basic and fundamental packing problem studied in the discrete optimization literature. It asks for an assignment of n jobs to a set of m identical machines that minimizes the makespan. The problem is strongly NPhard, and thus we do not expect a (1 + epsilon)-approximation algorithm with a running time that depends polynomially on 1/epsilon. Furthermore, Chen et al. [Chen/JansenZhang, SODA'13] recently showed that a running time of 2^{1/epsilon}^{1-delta} + poly(n) for any delta > 0 would imply that the Exponential Time Hypothesis (ETH) fails. A long sequence of algorithms have been developed that try to obtain low dependencies on 1/epsilon, the better of which achieves a running time of 2^{~O(1/epsilon^{2})} + O(n*log(n)) [Jansen, SIAM J. Disc. Math. 2010]. In this paper we obtain an algorithm with a running time of 2^{~O(1/epsilon)} + O(n*log(n)), which is tight under ETH up to logarithmic factors on the exponent. Our main technical contribution is a new structural result on the configuration-IP. More precisely, we show the existence of a highly symmetric and sparse optimal solution, in which all but a constant number of machines are assigned a configuration with small support. This structure can then be exploited by integer programming techniques and enumeration. We believe that our structural result is of independent interest and should find applications to other settings. In particular, we show how the structure can be applied to the minimum makespan problem on related machines and to a larger class of objective functions on parallel machines. For all these cases we obtain an efficient PTAS with running time 2^{~O(1/epsilon)} + poly(n).
Cite as

Klaus Jansen, Kim-Manuel Klein, and José Verschae. Closing the Gap for Makespan Scheduling via Sparsification Techniques. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 72:1-72:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ICALP.2016.72,
  author =	{Jansen, Klaus and Klein, Kim-Manuel and Verschae, Jos\'{e}},
  title =	{{Closing the Gap for Makespan Scheduling via Sparsification Techniques}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{72:1--72:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.72},
  URN =		{urn:nbn:de:0030-drops-62122},
  doi =		{10.4230/LIPIcs.ICALP.2016.72},
  annote =	{Keywords: scheduling, approximation, PTAS, makespan, ETH}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.135
Fully Dynamic Bin Packing Revisited

Authors: Sebastian Berndt, Klaus Jansen, and Kim-Manuel Klein

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of bins and migration factor, if we wish to achieve an asymptotic competitive ratio of 1 + epsilon for the number of bins, a relatively simple argument proves a lower bound of Omega(1/epsilon) of the migration factor. We establish a fairly close upper bound of O(1/epsilon^4 log(1/epsilon)) using a new dynamic rounding technique and new ideas to handle small items in a dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in the number of items n and in 1/epsilon. The previous best trade-off was for an asymptotic competitive ratio of 5/4 for the bins (rather than 1+epsilon) and needed an amortized number of O(log n) repackings (while in our scheme the number of repackings is independent of n and non-amortized).
Cite as

Sebastian Berndt, Klaus Jansen, and Kim-Manuel Klein. Fully Dynamic Bin Packing Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 135-151, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{berndt_et_al:LIPIcs.APPROX-RANDOM.2015.135,
  author =	{Berndt, Sebastian and Jansen, Klaus and Klein, Kim-Manuel},
  title =	{{Fully Dynamic Bin Packing Revisited}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{135--151},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.135},
  URN =		{urn:nbn:de:0030-drops-53008},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.135},
  annote =	{Keywords: online, bin packing, migration factor, robust, AFPTAS}
}
  • Refine by Author
  • 6 Klein, Kim-Manuel
  • 5 Jansen, Klaus
  • 1 Berndt, Sebastian
  • 1 Bilz, Raphael
  • 1 Brodal, Gerth Stølting
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Discrete optimization
  • 2 Theory of computation → Integer programming
  • 1 Computing methodologies → Modeling and simulation
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 2 bin packing
  • 2 migration factor
  • 1 AFPTAS
  • 1 Connected Components
  • 1 Diophantine approximation
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 3 2021
  • 1 2015
  • 1 2016
  • 1 2017
  • 1 2018
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact