Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

We are always looking for enthusiastic young people who are interested in a research project or thesis in the Bachelor, Master, and PhD programs. There are often topics available that are not listed here, so please contact us if you are interested in a project or thesis within an area of our group's research.

Contents

  • 1 192.105 (PR) Project in CS1: Team-Based Research in Algorithmics (6 ECTS) for 2020W
  • 2 Location Optimization of Battery Swapping Stations for Electric Scooters
  • 3 Cooperative Optimization Approaches for Distributing Service Points
  • 4 Solving Hard Combinatorial Problems with SAT and QBF Solvers
  • 5 Graph Drawing
  • 6 Algorithmic Cartography and Geometry

192.105 (PR) Project in CS1: Team-Based Research in Algorithmics (6 ECTS) for 2020W

In the upcoming winter semester 2020/2021, we are offering a research project Team-Based Research in Algorithmics (PR, 6 ECTS)!

Participants work in groups of size 2–3 in close cooperation with the advisors on a selected research
topic in algorithmic design. The project is conducted through
• intensive collaboration between group members,
• weekly meetings with the advisors,
• 2× presentations of the results,
• 1× write up of the results in a manuscript,
• 1× review of a paper of some other group.

During the project, they learn how to identify and tackle open questions, conduct independent scientific
research and present their own results, in both, oral and in written form. Ideally, if the original results
of a group are significant and promising, we plan to submit them to an international conference or
journal.
The maximum number of project participants is limited to six.

We will publish potential research topics in the first week of October, 2020. If you are interested
in the project, please write an email to jiehua.chen@tuwien.ac.at or register at TISS

https://tiss.tuwien.ac.at/course/educationDetails.xhtml?dswid=9277&dsrid=735&courseNr=192105&semester=2020W

The deadline of the registration of the project is October 11, 2020.

 

 

Location Optimization of Battery Swapping Stations for Electric
Scooters

Date: 13.07.2020
Topic for: Master Thesis, financial support available
Contact: Thomas Jatschka or Günther Raidl

Loading the batteries of electric vehicles is usually a time-consuming process that hinders the large-scale adoption of such vehicles.
For small vehicles such as electric scooters a possibility is to make batteries easily exchangeable for users and to provide enough battery swapping stations in the target area to cover the need for replacement batteries. At these battery swapping stations, the charging of returned batteries can take place without delaying any traveling, and sufficiently charged batteries are again provided to customers. In such a system, the geographic allocation of the swapping stations and
their dimensioning is critical. While typically one wants to minimize the costs for opening and maintaining the stations, the convenience for the users to exchange batteries along their usual routes should be maximized.
The problem is based on a real-world project from a partner in industry. For solving the problem methods from the area of metaheuristics and/or mixed integer linear programming shall be applied.

Cooperative Optimization Approaches for Distributing Service Points

Date: 11.02.2019
Topic for: Master Thesis
Contact: Thomas Jatschka or Günther Raidl

For many business models an optimal distribution of service points in a customer community is needed. Examples are charging/battery swapping stations of electric vehicles, bicycle/car sharing stations, and repair stations. When planning such systems, estimating under which conditions which customer demand can be fulfilled is fundamental in order to design and evaluate possible solutions. Such customer demands are usually acquired upfront e.g. using data on public transport, the street network, or surveys of potential customers. However, customer demand information determined in such ways typically is vague, and not uncommonly a system built on such assumptions is not as effective as originally hoped for due to major deviations in reality.

Alternative to acquiring demands upfront, cooperative optimization approaches incorporate potential users directly into the data acquisition as well as the optimization process. Expected benefits are a faster and cheaper data acquisition, the direct integration of users into the whole planning process, and ultimately better and more accepted optimization results. However, integrating users into the optimization progress also comes with some disadvantages. User interactions are not only considered time consuming but should also be treated as a scarce resource as a user is only willing to have a limited number of interactions with the program. A possible way to overcome these limitations is to use surrogate functions/machine learning techniques for simulating the interaction with a user.

 

Solving Hard Combinatorial Problems with SAT and QBF Solvers

Over the last two decades, SAT-solvers (which are programs that solve the Boolean satisfiability problem) have become surprisingly powerful and can check the satisfiability of instances with hundreds of thousands of variables in a few minutes. Among the most powerful SAT-solvers are Glucose and Lingeling.The subject for a Bachelor or Masters thesis would be to translate a hard combinatorial problem into SAT and solve it with a SAT-solver. For such a translation (often called encoding) there are usually many different approaches, and part of the thesis would be to compare different approaches experimentally on a set of problem instances.

The considered combinatorial problem can be chosen from a large pool of problems, including graph, clustering and optimization problems. Some recent research in this direction can be found here and here.

For even harder problems, like finding a winning strategy for a board game, one needs to go beyond SAT and use a QBF solver (Qute is such a solver we developed in our group).

Date: February 2018
Topic for: Bachelor/Master Theses
Contact: Stefan Szeider

Graph Drawing

Date: constantly
Topic for: Bachelor/Master Theses
Contact: Martin Nöllenburg

Graph Drawing is concerned with algorithms to compute geometric representations of graphs and networks. Applications of graph drawing range from graph visualizations for human users to hardware layouts and wireless routing. Scientifically, the area offers a wide spectrum of topics for student theses, from theoretical questions (e.g., existence of certain layouts or algorithms with certain properties) to practical questions of modeling the actual requirements of a particular application and designing, implementing, and evaluating algorithms for solving it.

Requirements:

  • Proficiency in (graph) algorithmics
  • Interest in geometry and visualization
  • Practical topics: good programming skills

Algorithmic Cartography and Geometry

Date: constantly
Topic for: Bachelor/Master Theses
Contact: Martin Nöllenburg

Digital cartography offers a wide spectrum of visualization problems that can be solved by geometric algorithms. The types of maps range from dynamic and interactive maps, e.g., on smart phones and mobile devices, to unconventional diagrammatic or schematic maps. Examples of algorithmic problems comprise label placement for map features, algorithms for constructing cartograms, or schematic destination maps. The area contains both topics with a stronger practical focus (including evaluation) or with a more theoretical focus. Thesis topics in computational geometry without direct links to cartography are also possible.

Requirements:

  • Proficiency in algorithmics and geometric algorithms
  • Interest in maps and interdisciplinary work
  • Practical topics: good programming skills

News

  • Martin Nöllenburg: promotion to Full Professor

    Martin Nöllenburg: promotion to Full Professor

    2020-12-17
    By December 1st, 2020, our colleague Martin Nöllenburg has been promoted to Full Professor for Graph and Geometric Algorithms.  Martin has …Read More »
  • Martin Kronegger wins the Best Teaching Award 2020

    Martin Kronegger wins the Best Teaching Award 2020

    2020-10-23
    Congratulations to Martin Kronegger who received a Best Teaching Award 2020 from TU Wien. The Algorithms and Complexity group is …Read More »
  • Welcome to our Feodor Lynen Fellow Dr. Manuel Sorge

    Welcome to our Feodor Lynen Fellow Dr. Manuel Sorge

    2020-10-12
    On October 1, 2020, Dr. Manuel Sorge has joined the Algorithms and Complexity group with a prestigious Feodor Lynen postdoc …Read More »
  • TU Wien students excel at the 2020 Graph Drawing Contest

    TU Wien students excel at the 2020 Graph Drawing Contest

    2020-10-01
    The 27th annual Graph Drawing Contest, held (virtually) in conjunction with the 28th International Symposium on Graph Drawing and Network …Read More »
  • Best Paper Award at CP’2020

    Best Paper Award at CP’2020

    2020-09-11
    Tomáš Peitl and Stefan Szeider won the Best Paper Award at the main track of CP'2020, the 26th International Conference on Principles …Read More »

News archive

All news for 2015, 2016, 2017, 2018 and 2019.
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.