Approximation Algorithms

Heuristic Approaches for Scheduling in Parallel Machine Environments

  • Kyriakos Bitsis
  • Konstantinos Kaparis
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Meta Heuristics Tags , ,

    Efficient and effective scheduling is crucial for ensuring the productivity and competitiveness of production lines, contributing significantly to organizational sustainability. This study addresses the scheduling challenges faced by a UK-based steel reinforcement manufacturer. We propose a heuristic algorithm to tackle a multistage flexible flow shop scheduling problem, where each stage consists of parallel unrelated machines. … Read more

    The alternating simultaneous Halpern-Lions-Wittmann-Bauschke algorithm for finding the best approximation pair for two disjoint intersections of convex sets

  • Yair Censor
  • Rafiq Mansour
  • Daniel Reem
    • Categories Approximation Algorithms, Constrained Nonlinear Optimization, Convex Optimization Tags , , , , ,

    Given two nonempty and disjoint intersections of closed and convex subsets, we look for a best approximation pair relative to them, i.e., a pair of points, one in each intersection, attaining the minimum distance between the disjoint intersections. We propose an iterative process based on projections onto the subsets which generate the intersections. The process … Read more

    Approximation Algorithms for Min-max-min Robust Optimization and K-Adaptability under Objective Uncertainty

  • Jannis Kurtz
    • Categories Approximation Algorithms, Robust Optimization Tags , , ,

    In this work we investigate the min-max-min robust optimization problem and the k-adaptability robust optimization problem for binary problems with uncertain costs. The idea of the first approach is to calculate a set of k feasible solutions which are worst-case optimal if in each possible scenario the best of the k solutions is implemented. It … Read more

    General Polyhedral Approximation of Two-Stage Robust Linear Programming

  • LukasGrunau
  • Tim Niemann
  • Sebastian Stiller
    • Categories Approximation Algorithms, Combinatorial Optimization, Robust Optimization Tags , , , ,

    \(\) We consider two-stage robust linear programs with a budget of uncertainty for the righthand side. In this scenario set, which is frequently used in robust optimization, the uncertain righthand side for each row lies in an interval and the relative increases summed over all rows are less than a budget \(\Gamma\). We develop a … Read more

    Finding Groups with Maximum Betweenness Centrality via Integer Programming with Random Path Sampling

  • Tomas Lagos
  • Oleg A. Prokopyev
  • Alexander Veremyev
    • Categories Approximation Algorithms, Graphs and Matroids, Stochastic Approaches Tags , , , ,

    One popular approach to access the importance/influence of a group of nodes in a network is based on the notion of centrality. For a given group, its group betweenness centrality is computed, first, by evaluating a ratio of shortest paths between each node pair in a network that are “covered” by at least one node … Read more

    Worst-Case Analysis of Heuristic Approaches for the Temporal Bin Packing Problem with Fire-Ups

  • John Martinovic
  • Nico Strasdat
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Scheduling Tags , , , ,

    We consider the temporal bin packing problem with fire-ups (TBPP-FU), a branch of operations research recently introduced in multi-objective cloud computing. In this scenario, any item is equipped with a resource demand and a lifespan meaning that it requires the bin capacity only during that time interval. We then aim at finding a schedule minimizing … Read more

    Ordering integers under different permutations

  • Akshay Gupte
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , , ,

    \(\) The question of finding the largest integer contained between two given lists of integers is trivial when integer ordering is interpreted in its usual way. We propose a nontrivial variant wherein each ordering comparison is performed after integers have been mapped under some bijection, and analyze the computational complexity of our combinatorial problem under … Read more

    Submodular Dispatching

  • Ignacio Erazo
  • Alejandro Toriello
    • Categories Approximation Algorithms, Production and Logistics, Transportation Tags , , ,

    Motivated by applications in e-commerce logistics where orders or items arrive at different times and must be dispatched or processed in batches, we propose the submodular dispatching problem (SMD), a strongly NP-hard model defined by a set of orders with release times and a non-decreasing submodular dispatch time function. A single uncapacitated vehicle must dispatch … Read more

    An approximation algorithm for optimal piecewise linear approximations of bounded variable products

  • Lukas Hager
  • Robert Burlacu
  • Andreas Bärmann
  • Katja Kutzer
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Quadratic Programming Tags , , ,

    We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as … Read more

    Approximation algorithm for the two-stage stochastic set multicover problem with simple resource

  • Yotaro Takazawa
    • Categories Approximation Algorithms, Stochastic Programming Tags , , ,

    We study a two-stage, finite-scenarios stochastic version of the set multicover problem, where there is uncertainty about a demand for each element to be covered and the penalty cost is imposed linearly on the shortfall in each demand. This problem is NP-hard and has an application in shift scheduling in crowdsourced delivery services. For this … Read more