BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Martin Böhm

Martin Böhm appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and Algorithms

Catalog footprint

What is connected

5works
1topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2016arXiv

A Two-Phase Algorithm for Bin Stretching with Stretching Factor 1.5

Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for Online Bin Stretching with a stretching factor of 1.5 for any number of bins. We build on previous algorithms and use a two-phase approach. However, our analysis is technically more complicated and uses amortization over the bins with the help of two weight functions.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Online Algorithms for Multi-Level Aggregation

In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests. Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4 2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. We also show several additional lower and upper bound results for some special cases of MLAP, including the Single-Phase variant and the case when the tree is a path.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Online Bin Stretching with Three Bins

Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for Online Bin Stretching with a stretching factor of $11/8 = 1.375$ for three bins. Additionally, we present a lower bound of $45/33 = 1.\overline{36}$ for Online Bin Stretching on three bins and a lower bound of $19/14$ for four and five bins that were discovered using a computer search.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Online Packet Scheduling with Bounded Delay and Lookahead

We study the online bounded-delay packet scheduling problem (BDPS), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature, yet its optimal competitive ratio remains unknown: the best upper bound is $1.828$, still quite far from the best lower bound of $ϕ\approx 1.618$. In the variant of BDPS with $s$-bounded instances, each packet can be scheduled in at most $s$ consecutive slots, starting at its release time. The lower bound of $ϕ$ applies even to the special case of $2$-bounded instances, and a $ϕ$-competitive algorithm for $3$-bounded instances was given in Chin et al. Improving that result, and addressing a question posed by Goldwasser, we present a $ϕ$-competitive algorithm for $4$-bounded instances. We also study a variant of BDPS where an online algorithm has the additional power of $1$-lookahead, knowing at time $t$ which packets will arrive at time $t+1$. For BDPS with $1$-lookahead restricted to $2$-bounded instances, we present an online algorithm with competitive ratio $(\sqrt{13} - 1)/2 \approx 1.303$ and we prove a nearly tight lower bound of $(1 + \sqrt{17})/4 \approx 1.281$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Online Colored Bin Packing

In the Colored Bin Packing problem a sequence of items of sizes up to $1$ arrives to be packed into bins of unit capacity. Each item has one of $c\geq 2$ colors and an additional constraint is that we cannot pack two items of the same color next to each other in the same bin. The objective is to minimize the number of bins. In the important special case when all items have size zero, we characterize the optimal value to be equal to color discrepancy. As our main result, we give an (asymptotically) 1.5-competitive algorithm which is optimal. In fact, the algorithm always uses at most $\lceil1.5\cdot OPT\rceil$ bins and we show a matching lower bound of $\lceil1.5\cdot OPT\rceil$ for any value of $OPT\geq 2$. In particular, the absolute ratio of our algorithm is $5/3$ and this is optimal. For items of unrestricted sizes we give an asymptotically $3.5$-competitive algorithm. When the items have sizes at most $1/d$ for a real $d \geq 2$ the asymptotic competitive ratio is $1.5+d/(d-1)$. We also show that classical algorithms First Fit, Best Fit and Worst Fit are not constant competitive, which holds already for three colors and small items. In the case of two colors---the Black and White Bin Packing problem---we prove that all Any Fit algorithms have absolute competitive ratio $3$. When the items have sizes at most $1/d$ for a real $d \geq 2$ we show that the Worst Fit algorithm is absolutely $(1+d/(d-1))$-competitive.

0 citations0 reviewsNo code linkedOpen access