Filters

Settings

Now showing1 - 5 of 5
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Project, Access status: without files ,
      64
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Project, Access status: without files ,
      88
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Project, Access status: without files ,
    Simultaneous approximation of multi-criteria optimization problems
    In this project, the researchers develop general-purpose algorithmic methods for finding optimal and near-optimal solutions to complex multi-criteria optimization problems arising in social choice scenarios. Our algorithms will be fully multivariate to harness the structures inherent to data sets from diverse domains, and come with provable guarantees on their run time and the quality of the produced solution. With these properties, they improve upon the vast body of ad-hoc implementations currently available, which are often data-specific, or lack robust guarantees on run time and solution quality.
      59
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Project, Access status: without files ,
    Kernelization for Big Data
    The main research goal of this project is the quest for a rigorous mathematical theory of input-output efficient preprocessing. This new theory will develop the computational tools to design powerful algorithms for preprocessing very large instances of hard problems that very efficiently compress those instances to smaller ones with guaranteed size. Our motivation is the incapability of current preprocessing routines with compression guarantee (kernelizations) to handle very large instances that do not fit into main memory. The theory also seeks to rigorously explain the practical successes of preprocessing very large instances by algorithms without compression guarantee (heuristics), and will lead to a concept of computational intractability to explain the limitations of heuristics. The project aims to design preprocessing algorithms that harness the full capabilities of advanced processor technology and memory hierarchies of computing hardware in science and industry, to efficiently compress big data sets. With new multivariate computational models that utilize instance structure and hardware structure at the same time, we will deepen the understanding of the mathematical origins of compressibility and serve to build more powerful algorithms for preprocessing massive data sets.
      1582
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Project, Access status: without files ,
    Multivariate Algorithms for High Multiplicity Scheduling
    Scheduling and planning problems belong to the fundamental questions in algorithms. Many of those problems are highly unlikely to admit procedures that guarantee to deliver an optimal solution in polynomial time. Therefore, hundreds of approximation algorithms have been developed for such problems in the past decades.In this project we deal with an alternative approach for scheduling problems with high multiplicity, in which a large number of jobs must be planned which can be categorized into few categories. Such problems arise in, for instance, sequencing of landing aircraft, whose safety separation distances mainly depend on which of few aircraft type the respective planes belong to. Our goal is the development of fixed-parameter algorithms, which deliver optimal solutions in time that depends polynomially on the input size and superpolynomially only in the small number of categories. This way, we generalize polynomial-time algorithms for special cases of those problems with only constantly many job categories to more realistic models, and simultaneously improve the run times of fixed-parameter algorithms which so far require a lavish encoding of every single job.
      1382