The Compact Genetic Algorithm Struggles on Cliff Functions Frank NeumannDirk SudholtCarsten Witt OriginalPaper Open access 17 November 2024
Partition Strategies for the Maker–Breaker Domination Game Guillaume BaganEric DuchêneAline Parreau OriginalPaper 15 November 2024
Optimal Algorithms for Online b-Matching with Variable Vertex Capacities Susanne AlbersSebastian Schubert OriginalPaper Open access 08 November 2024
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure Hans L. BodlaenderCarla GroenlandPaloma T. Lima OriginalPaper Open access 04 November 2024
Better Hardness Results for the Minimum Spanning Tree Congestion Problem Huong LuuMarek Chrobak OriginalPaper Open access 26 October 2024
Euclidean Maximum Matchings in the Plane—Local to Global Ahmad BiniazAnil MaheshwariMichiel Smid OriginalPaper 19 October 2024
Online Paging with Heterogeneous Cache Slots Marek ChrobakSamuel HaneyNeal E. Young OriginalPaper Open access 17 October 2024
Anti-factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard) Dániel MarxGovind S. SankarPhilipp Schepper OriginalPaper Open access 15 October 2024
Energy Constrained Depth First Search Shantanu DasDariusz DereniowskiPrzemysław Uznański OriginalPaper Open access 12 October 2024 Pages: 3759 - 3782
On Scheduling Mechanisms Beyond the Worst Case Yansong GaoJie Zhang OriginalPaper Open access 12 October 2024
Recovering the Original Simplicity: Succinct and Exact Quantum Algorithm for the Welded Tree Problem Guanzhong LiLvzhou LiJingquan Luo OriginalPaper 04 October 2024 Pages: 3719 - 3758
Permutation-constrained Common String Partitions with Applications Manuel LafondBinhai Zhu OriginalPaper 30 September 2024 Pages: 3684 - 3718
Reachability of Fair Allocations via Sequential Exchanges Ayumi IgarashiNaoyuki KamiyamaSheung Man Yuen OriginalPaper Open access 21 September 2024 Pages: 3653 - 3683
On Flipping the Fréchet Distance Omrit FiltserMayank GoswamiValentin Polishchuk OriginalPaper 20 September 2024 Pages: 3629 - 3652
Semi-streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints Chien-Chung HuangFrançois Sellier OriginalPaper 14 September 2024 Pages: 3598 - 3628
On the Parameterized Complexity of Compact Set Packing Ameet Gadekar OriginalPaper Open access 13 September 2024 Pages: 3579 - 3597
Ultimate Greedy Approximation of Independent Sets in Subcubic Graphs Piotr KrystaMathieu MariNan Zhi OriginalPaper 12 September 2024 Pages: 3518 - 3578
Testing Connectedness of Images Piotr BermanMeiram MurzabulatovDragos-Florian Ristache OriginalPaper 12 September 2024 Pages: 3496 - 3517
Romeo and Juliet Meeting in Forest Like Regions Neeldhara MisraManas MulpuriGaurav Viramgami OriginalPaper 03 September 2024 Pages: 3465 - 3495
Connected k-Center and k-Diameter Clustering Lukas DrexlerJan EubeJulian Wargalla OriginalPaper Open access 02 September 2024 Pages: 3425 - 3464
Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited Tatsuya GimaTakehiro ItoYota Otachi OriginalPaper 02 September 2024 Pages: 3395 - 3424
A Framework for Adversarial Streaming Via Differential Privacy and Difference Estimators Idan AttiasEdith CohenUri Stemmer Research Open access 31 August 2024 Pages: 3339 - 3394
Reconfiguring Shortest Paths in Graphs Kshitij GajjarAgastya Vibhuti JhaAbhiruk Lahiri OriginalPaper Open access 27 August 2024 Pages: 3309 - 3338
Parameterized Complexity of Reconfiguration of Atoms Alexandre CooperStephanie MaazNaomi Nishimura OriginalPaper 26 August 2024 Pages: 3284 - 3308
Runtime Analysis of Quality Diversity Algorithms Jakob BossekDirk Sudholt OriginalPaper Open access 13 August 2024 Pages: 3252 - 3283
On the Parameterized Complexity of Bend-Minimum Orthogonal Planarity Emilio Di GiacomoWalter DidimoGiacomo Ortali OriginalPaper Open access 04 August 2024 Pages: 3231 - 3251
The Complexity of Finding and Enumerating Optimal Subgraphs to Represent Spatial Correlation Jessica EnrightDuncan LeeJohn Sylvester OriginalPaper Open access 31 July 2024 Pages: 3186 - 3230
Limitations of the Impagliazzo–Nisan–Wigderson Pseudorandom Generator Against Permutation Branching Programs William M. HozaEdward PyneSalil Vadhan OriginalPaper Open access 29 July 2024 Pages: 3153 - 3185
Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions Carola DoerrDuri Andrea JanettJohannes Lengler OriginalPaper 22 July 2024 Pages: 3115 - 3152
Minimizing Energy Consumption for Real-Time Tasks on Heterogeneous Platforms Under Deadline and Reliability Constraints Yiqin GaoLi HanFrédéric Vivien OriginalPaper 22 July 2024 Pages: 3079 - 3114
On a Traveling Salesman Problem for Points in the Unit Cube József BaloghFelix Christian ClemenAdrian Dumitrescu OriginalPaper Open access 18 July 2024 Pages: 3054 - 3078
Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time David Eppstein OriginalPaper Open access 18 July 2024 Pages: 3027 - 3053
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling Spencer ComptonSlobodan MitrovićRonitt Rubinfeld OriginalPaper 18 July 2024 Pages: 2997 - 3026
Sublinear Algorithms in T-Interval Dynamic Networks Irvan JahjaHaifeng Yu OriginalPaper 12 July 2024 Pages: 2959 - 2996
Stagnation Detection in Highly Multimodal Fitness Landscapes Amirhossein RajabiCarsten Witt OriginalPaper Open access 02 July 2024 Pages: 2929 - 2958
Parameterized Complexity of Streaming Diameter and Connectivity Problems Jelle J. OostveenErik Jan van Leeuwen OriginalPaper Open access 19 June 2024 Pages: 2885 - 2928
Approximation Algorithms for the Two-Watchman Route in a Simple Polygon Bengt J. NilssonEli Packer OriginalPaper Open access 19 June 2024 Pages: 2845 - 2884
Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix Multiplication David G. Harris OriginalPaper 17 June 2024 Pages: 2822 - 2844
Online Unit Profit Knapsack with Predictions Joan BoyarLene M. FavrholdtKim S. Larsen OriginalPaper Open access 13 June 2024 Pages: 2786 - 2821
Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle Argyrios DeligkasGeorge B. MertziosViktor Zamaraev OriginalPaper Open access 12 June 2024 Pages: 2766 - 2785
Online Geometric Covering and Piercing Minati DeSaksham JainSatyam Singh OriginalPaper 03 June 2024 Pages: 2739 - 2765
Slim Tree-Cut Width Robert GanianViktoriia Korchemna OriginalPaper Open access 01 June 2024 Pages: 2714 - 2738
Approximating Long Cycle Above Dirac’s Guarantee Fedor V. FominPetr A. GolovachKirill Simonov OriginalPaper Open access 30 May 2024 Pages: 2676 - 2713
New Algorithms for Steiner Tree Reoptimization Davide Bilò OriginalPaper Open access 29 May 2024 Pages: 2652 - 2675
Approximation Algorithms for Covering Vertices by Long Paths Mingyang GongBrett EdgarEiji Miyano OriginalPaper 28 May 2024 Pages: 2625 - 2651
Parity Permutation Pattern Matching Virginia Ardévol MartínezFlorian SikoraStéphane Vialette OriginalPaper 22 May 2024 Pages: 2605 - 2624
Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions Ishan BansalJoseph CheriyanSharat Ibrahimpur OriginalPaper 20 May 2024 Pages: 2575 - 2604
Parameterized Approximation Algorithms and Lower Bounds for k-Center Clustering and Variants Sayan BandyapadhyayZachary FriggstadRamin Mousavi OriginalPaper 13 May 2024 Pages: 2557 - 2574
Sample-Based Distance-Approximation for Subsequence-Freeness Omer Cohen SidonDana Ron OriginalPaper Open access 13 May 2024 Pages: 2519 - 2556
Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus Benjamin DoerrAndrew James Kelley OriginalPaper 10 May 2024 Pages: 2479 - 2518
