Andreas Wiese

CoRR, 2024

On Approximation Schemes for Stabbing Rectilinear Polygons.

[BibT_eX]

[DOI]

CoRR, 2024

Simpler constant factor approximation algorithms for weighted flow time - now for any p-norm.

[BibT_eX]

[DOI]

Alexander Armbruster

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

A (3 + ɛ)-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Fixed-Parameter Algorithms for Unsplittable Flow Cover.

[BibT_eX]

[DOI]

Andrés Cristi

Mathieu Mari

Theory Comput. Syst., February, 2023

A (3+ε)-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds.

[BibT_eX]

[DOI]

CoRR, 2023

Simpler constant factor approximation algorithms for weighted flow time - now for any p-norm.

[BibT_eX]

[DOI]

Alexander Armbruster

CoRR, 2023

Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries.

[BibT_eX]

[DOI]

MohammadHossein Bateni

Hossein Esfandiari

Hendrik Fichtenberger

CoRR, 2023

A PTAS for Minimizing Weighted Flow Time on a Single Machine.

[BibT_eX]

[DOI]

Alexander Armbruster

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries.

[BibT_eX]

[DOI]

MohammadHossein Bateni

Hossein Esfandiari

Hendrik Fichtenberger

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Exact and Approximation Algorithms for Routing a Convoy Through a Graph.

[BibT_eX]

[DOI]

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Computational Geometry, 2023

2022

A PTAS for unsplittable flow on a path.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Unsplittable Flow on a Path: The Game!.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

A 3-Approximation Algorithm for Maximum Independent Set of Rectangles.

[BibT_eX]

[DOI]

Madhusudhan Reddy Pittu

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

A PTAS for the Horizontal Rectangle Stabbing Problem.

[BibT_eX]

[DOI]

Arindam Khan

Aditya Subramanian

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Approximation Algorithms for Round-UFP and Round-SAP.

[BibT_eX]

[DOI]

Debajyoti Kar

Arindam Khan

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

A Simpler QPTAS for Scheduling Jobs with Precedence Constraints.

[BibT_eX]

[DOI]

Syamantak Das

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Approximating Geometric Knapsack via L-packings.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

On fully dynamic constant-factor approximation algorithms for clustering problems.

[BibT_eX]

[DOI]

Hendrik Fichtenberger

Monika Henzinger

CoRR, 2021

A 4-Approximation Algorithm for Maximum Independent Set of Rectangles.

[BibT_eX]

[DOI]

Madhusudhan Reddy Pittu

CoRR, 2021

A (2 + ε)-approximation algorithm for preemptive weighted flow time on a single machine.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Additive Approximation Schemes for Load Balancing Problems.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time.

[BibT_eX]

[DOI]

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees.

[BibT_eX]

[DOI]

Tomás Martínez-Muñoz

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Faster (1+ε)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Computational Geometry, 2021

On Guillotine Separable Packings for the Two-Dimensional Geometric Knapsack Problem.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020

On the extension complexity of scheduling polytopes.

[BibT_eX]

[DOI]

Hans Raj Tiwary

Victor Verdugo

Oper. Res. Lett., 2020

Breaking symmetries to rescue sum of squares in the case of makespan scheduling.

[BibT_eX]

[DOI]

Victor Verdugo

José Verschae

Math. Program., 2020

A (2+ε)-approximation algorithm for preemptive weighted flow time on a single machine.

[BibT_eX]

[DOI]

CoRR, 2020

Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time.

[BibT_eX]

[DOI]

CoRR, 2020

Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity.

[BibT_eX]

[DOI]

Monika Henzinger

Stefan Neumann

CoRR, 2020

Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs.

[BibT_eX]

[DOI]

Michal Pilipczuk

Erik Jan van Leeuwen

Algorithmica, 2020

Better Approximations for General Caching and UFP-Cover Under Resource Augmentation.

[BibT_eX]

[DOI]

Andrés Cristi

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

Breaking the Barrier of 2 for the Storage Allocation Problem.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

On the Two-Dimensional Knapsack Problem for Convex Polygons.

[BibT_eX]

[DOI]

Arturo I. Merino

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.

[BibT_eX]

[DOI]

Monika Henzinger

Stefan Neumann

Proceedings of the 36th International Symposium on Computational Geometry, 2020

2019

A Generalized Parallel Task Model for Recurrent Real-Time Processes.

[BibT_eX]

[DOI]

Leen Stougie

ACM Trans. Parallel Comput., 2019

Faster Approximation Schemes for the Two-Dimensional Knapsack Problem.

[BibT_eX]

[DOI]

Sandy Heydrich

ACM Trans. Algorithms, 2019

Approximation Schemes for Independent Set and Sparse Subsets of Polygons.

[BibT_eX]

[DOI]

Sariel Har-Peled

J. ACM, 2019

On the extension complexity of scheduling.

[BibT_eX]

[DOI]

Hans Raj Tiwary

Victor Verdugo

CoRR, 2019

Packing Cars into Narrow Roads: PTASs for Limited Supply Highway.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack.

[BibT_eX]

[DOI]

Stefan Kratsch

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

A Mazing 2+ϵ Approximation for Unsplittable Flow on a Path.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Semidefinite and linear programming integrality gaps for scheduling identical machines.

[BibT_eX]

[DOI]

Math. Program., 2018

Submodular unsplittable flow on trees.

[BibT_eX]

[DOI]

Math. Program., 2018

Independent Set of Convex Polygons: From $$n^{\epsilon }$$ n ϵ to $$1+\epsilon $$ 1 + ϵ via Shrinking.

[BibT_eX]

[DOI]

Algorithmica, 2018

How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions.

[BibT_eX]

[DOI]

Wiebke Höhn

Julián Mestre

Algorithmica, 2018

A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Fixed-Parameter Approximation Schemes for Weighted Flowtime.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking.

[BibT_eX]

[DOI]

Michal Pilipczuk

Erik Jan van Leeuwen

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

A (1+epsilon)-Approximation for Unsplittable Flow on a Path in Fixed-Parameter Running Time.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

A QPTAS for the General Scheduling Problem with Identical Release Dates.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

On Minimizing the Makespan When Some Jobs Cannot Be Assigned on the Same Machine.

[BibT_eX]

[DOI]

Syamantak Das

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

The Power of Recourse for Online MST and TSP.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Identification of key player genes in gene regulatory networks.

[BibT_eX]

[DOI]

BMC Syst. Biol., 2016

On approximating strip packing with a better ratio than 3/2.

[BibT_eX]

[DOI]

Giorgi Nadiradze

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Independent Set of Convex Polygons: From nϵ to 1+ϵ via Shrinking.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2016: Theoretical Informatics, 2016

This House Proves That Debating is Harder Than Soccer.

[BibT_eX]

[DOI]

Stefan Neumann

Proceedings of the 8th International Conference on Fun with Algorithms, 2016

2015

Scheduling and fixed-parameter tractability.

[BibT_eX]

[DOI]

Matthias Mnich

Math. Program., 2015

Assigning sporadic tasks to unrelated machines.

[BibT_eX]

[DOI]

Cyriel Rutten

Suzanne van der Ster

Math. Program., 2015

Scheduling with an Orthogonal Resource Constraint.

[BibT_eX]

[DOI]

Martin Niemeier

Algorithmica, 2015

New Approximation Schemes for Unsplittable Flow on a Path.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

A (2+\epsilon ) ( 2 + ϵ ) -Approximation Algorithm for the Storage Allocation Problem.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking.

[BibT_eX]

[DOI]

Parinya Chalermsook

Proceedings of the Approximation, 2015

On Guillotine Cutting Sequences.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths.

[BibT_eX]

[DOI]

Paul S. Bonsma

Jens Schulz

SIAM J. Comput., 2014

On the configuration-LP for scheduling on unrelated machines.

[BibT_eX]

[DOI]

José Verschae

J. Sched., 2014

A Mazing 2+∊ Approximation for Unsplittable Flow on a Path.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

Partitioned EDF scheduling on a few types of unrelated multiprocessors.

[BibT_eX]

[DOI]

Real Time Syst., 2013

Competitive-Ratio Approximation Schemes for Minimizing the Makespan in the Online-List Model

[BibT_eX]

[DOI]

Nicole Megow

CoRR, 2013

Scheduling Meets Fixed-Parameter Tractability.

[BibT_eX]

[DOI]

Matthias Mnich

CoRR, 2013

A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks.

[BibT_eX]

[DOI]

Nicole Megow

Proceedings of the IEEE 34th Real-Time Systems Symposium, 2013

Approximating the Configuration-LP for Minimizing Weighted Sum of Completion Times on Unrelated Machines.

[BibT_eX]

[DOI]

Maxim Sviridenko

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Approximation Schemes for Maximum Weight Independent Set of Rectangles.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Feasibility Analysis in the Sporadic DAG Task Model.

[BibT_eX]

[DOI]

Proceedings of the 25th Euromicro Conference on Real-Time Systems, 2013

2012

Feasibility Tests for Recurrent Real-Time Tasks in the Sporadic DAG Model

[BibT_eX]

[DOI]

CoRR, 2012

A Mazing 2+eps Approximation for Unsplittable Flow on a Path

[BibT_eX]

[DOI]

CoRR, 2012

Scheduling Unrelated Machines of Few Different Types

[BibT_eX]

[DOI]

CoRR, 2012

A Generalized Parallel Task Model for Recurrent Real-time Processes.

[BibT_eX]

[DOI]

Leen Stougie

Proceedings of the 33rd IEEE Real-Time Systems Symposium, 2012

Assigning Sporadic Tasks to Unrelated Parallel Machines.

[BibT_eX]

[DOI]

Cyriel Rutten

Suzanne van der Ster

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Packet routing and scheduling.

[BibT_eX]

[DOI]

PhD thesis, 2011

Local algorithms for edge colorings in UDGs.

[BibT_eX]

[DOI]

Iyad A. Kanj

Fenghui Zhang

Theor. Comput. Sci., 2011

Real-time Avionics Optimization.

[BibT_eX]

[DOI]

it Inf. Technol., 2011

Analysing local algorithms in location-aware quasi-unit-disk graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2011

Universal Packet Routing with Arbitrary Bandwidths and Transit Times.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Partitioned Real-time Scheduling on Heterogeneous Shared-Memory Multiprocessors.

[BibT_eX]

[DOI]

Martin Niemeier

Proceedings of the 23rd Euromicro Conference on Real-Time Systems, 2011

2010

Throughput Maximization for Periodic Packet Routing on Trees and Grids.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

Packet Routing on the Grid.

[BibT_eX]

[DOI]

Martin Skutella

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

Increasing Speed Scheduling and Flow Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Policies for Periodic Packet Routing.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

Scheduling periodic tasks in a hard real-time environment.

[BibT_eX]

[DOI]

Proceedings of the Scheduling, 14.02. - 19.02.2010, 2010

2009

Optimal movement of mobile sensors for barrier coverage of a planar region.

[BibT_eX]

[DOI]

Binay K. Bhattacharya

Theor. Comput. Sci., 2009

Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs.

[BibT_eX]

[DOI]

Discret. Math. Algorithms Appl., 2009

Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs?

[BibT_eX]

[DOI]

Ad Hoc Sens. Wirel. Networks, 2009

Packet Routing: Complexity and Algorithms.

[BibT_eX]

[DOI]

Martin Skutella

Proceedings of the Approximation and Online Algorithms, 7th International Workshop, 2009

Real-Time Message Routing and Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Impact of Locality on Location Aware Unit Disk Graphs.

[BibT_eX]

[DOI]

Algorithms, 2008

Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

Communication in wireless networks with directional antennas.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2008

Local Maximal Matching and Local 2-Approximation for Vertex Cover in UDGs.

[BibT_eX]

[DOI]