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

Christina Büsing

Christina Büsing appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCData Structures and AlgorithmsDiscrete Mathematicsmath.NANumerical Analysis

Catalog footprint

What is connected

7works
5topics
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

7 published item(s)

preprint2025arXiv

A Faster Parametric Search for the Integral Quickest Transshipment Problem

Algorithms for computing fractional solutions to the quickest transshipment problem have been significantly improved since Hoppe and Tardos first solved the problem in strongly polynomial time. For integral solutions, runtime improvements are limited to general progress on submodular function minimization, which is an integral part of Hoppe and Tardos' algorithm. Yet, no structural improvements on their algorithm itself have been proposed. We replace two central subroutines in the algorithm with methods that require vastly fewer minimizations of submodular functions. This improves the state-of-the-art runtime from $ \tilde{O}(m^4 k^{15}) $ down to $ \tilde{O}(m^2 k^5 + m^4 k^2) $, where $ k $ is the number of terminals and $ m $ is the number of arcs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Robust transshipment problem under consistent flow constraints

In this paper, we study robust transshipment under consistent flow constraints. We consider demand uncertainty represented by a finite set of scenarios and characterize a subset of arcs as so-called fixed arcs. In each scenario, we require an integral flow that satisfies the respective flow balance constraints. In addition, on each fixed arc, we require equal flow for all scenarios. The objective is to minimize the maximum cost occurring among all scenarios. We show that the problem is strongly NP-hard on acyclic digraphs by a reduction from the $(3,B2)$-SAT problem. Furthermore, we prove that the problem is weakly NP-hard on series-parallel digraphs by a reduction from a special case of the \textsc{Partition} problem. If in addition the number of scenarios is constant, we observe the pseudo-polynomial-time solvability of the problem. We provide polynomial-time algorithms for three special cases on series-parallel digraphs. Finally, we present a polynomial-time algorithm for pearl digraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Robust Minimum Cost Flow Problem Under Consistent Flow Constraints

The robust minimum cost flow problem under consistent flow constraints (RobMCF$\equiv$) is a new extension of the minimum cost flow (MCF) problem. In the RobMCF$\equiv$ problem, we consider demand and supply that are subject to uncertainty. For all demand realizations, however, we require that the flow value on an arc needs to be equal if it is included in the predetermined arc set given. The objective is to find feasible flows that satisfy the equal flow requirements while minimizing the maximum occurring cost among all demand realizations. In the case of a discrete set of scenarios, we derive structural results which point out the differences with the polynomial time solvable MCF problem on networks with integral capacities. In particular, the Integral Flow Theorem of Dantzig and Fulkerson does not hold. For this reason, we require integral flows in the entire paper. We show that the RobMCF$\equiv$ problem is strongly $\mathcal{NP}$-hard on acyclic digraphs by a reduction from the $(3,B2)$-Sat problem. Further, we demonstrate that the RobMCF$\equiv$ problem is weakly $\mathcal{NP}$-hard on series-parallel digraphs by providing a reduction from Partition and a pseudo-polynomial algorithm based on dynamic programming. Finally, we propose a special case on series-parallel digraphs for which we can solve the RobMCF$\equiv$ problem in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Robust strategic planning for mobile medical units with steerable and unsteerable demands

Mobile medical units (MMUs) are customized vehicles fitted with medical equipment that are used to provide primary care in rural environments. As MMUs can be easily relocated, they enable a demand-oriented, flexible, and local provision of health services. In this paper, we investigate the strategic planning of an MMU service by deciding where MMU operation sites should be set up and how often these should be serviced. To that end, we study the strategic planning problem for MMUs (SPMMU) $-$ a capacitated set covering problem that includes existing practices and two types of patient demands: (i) steerable demands representing patients who seek health services through a centralized appointment system and can be steered to any treatment facility within a given consideration set and (ii) unsteerable demands representing walk-in patients who always visit the closest available treatment facility. We propose an integer linear program for the SPMMU that can be solved via Benders decomposition and constraint generation. Starting from this formulation, we focus on the uncertain version of the problem in which steerable and unsteerable demands are modeled as random variables that may vary within a given interval. Using methods from robust optimization and duality theory, we devise exact constraint generation methods to solve the robust counterparts for interval and budgeted uncertainty sets. All our results transfer to the session-specific SPMMU and we evaluate our models in a computational study based on a set of instances generated from a rural primary care system in Germany.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Reference Point Methods and Approximation in Multicriteria Optimization

Operations research applications often pose multicriteria problems. Mathematical research on multicriteria problems predominantly revolves around the set of Pareto optimal solutions, while in practice, methods that output a single solution are more widespread. In real-world multicriteria optimization, reference point methods are widely used and successful examples of such methods. A reference point solution is the solution closest to a given reference point in the objective space. We study the approximation of reference point solutions. In particular, we establish that approximating reference point solutions is polynomially equivalent to approximating the Pareto set. Complementing these results, we show for a number of general algorithmic techniques in single criteria optimization how they can be lifted to reference point optimization. In particular, we lift the link between dynamic programming and FPTAS, as well as oblivious LP-rounding techniques. The latter applies, e.g., to Set Cover and several machine scheduling problems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Robust Optimization under Multi-band Uncertainty - Part I: Theory

The classical single-band uncertainty model introduced by Bertsimas and Sim has represented a breakthrough in the development of tractable robust counterparts of Linear Programs. However, adopting a single deviation band may be too limitative in practice: in many real-world problems, observed deviations indeed present asymmetric distributions over asymmetric ranges, so that getting a higher modeling resolution by partitioning the band into multiple sub-bands is advisable. The critical aim of our work is to close the knowledge gap on the adoption of multi-band uncertainty in Robust Optimization: a general definition and intensive theoretical study of a multi-band model are actually still missing. Our new developments have been also strongly inspired and encouraged by our industrial partners, interested in getting a better modeling of arbitrary shaped distributions, built on historical data about the uncertainty affecting the considered real-world problems.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

New results about multi-band uncertainty in Robust Optimization

"The Price of Robustness" by Bertsimas and Sim represented a breakthrough in the development of a tractable robust counterpart of Linear Programming Problems. However, the central modeling assumption that the deviation band of each uncertain parameter is single may be too limitative in practice: experience indeed suggests that the deviations distribute also internally to the single band, so that getting a higher resolution by partitioning the band into multiple sub-bands seems advisable. The critical aim of our work is to close the knowledge gap about the adoption of a multi-band uncertainty set in Robust Optimization: a general definition and intensive theoretical study of a multi-band model are actually still missing. Our new developments have been also strongly inspired and encouraged by our industrial partners, which have been interested in getting a better modeling of arbitrary distributions, built on historical data of the uncertainty affecting the considered real-world problems. In this paper, we study the robust counterpart of a Linear Programming Problem with uncertain coefficient matrix, when a multi-band uncertainty set is considered. We first show that the robust counterpart corresponds to a compact LP formulation. Then we investigate the problem of separating cuts imposing robustness and we show that the separation can be efficiently operated by solving a min-cost flow problem. Finally, we test the performance of our new approach to Robust Optimization on realistic instances of a Wireless Network Design Problem subject to uncertainty.

0 citations0 reviewsNo code linkedOpen access