Polynomial-time data reduction for weighted problems beyond additive goal functions
From MaRDI portal
Publication:2685700
DOI10.1016/j.dam.2022.11.018OpenAlexW4312206552MaRDI QIDQ2685700
René van Bevern, André Nichterlein, Matthias Bentert, Till Fluschnik, Rolf Niedermeier
Publication date: 22 February 2023
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1910.00277
partitioningschedulingroutingNP-hard problemscomputational social choiceproblem kernelizationweight reduction
Mathematical programming (90Cxx) Theory of computing (68Qxx) Operations research and management science (90Bxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial kernels for weighted problems
- New algorithms for minimizing the weighted number of tardy jobs on a single machine
- Interval scheduling and colorful independent sets
- An application of simultaneous diophantine approximation in combinatorial optimization
- Factoring polynomials with rational coefficients
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Parameterized complexity of machine scheduling: 15 open problems
- Constant-factor approximations for capacitated arc routing without triangle inequality
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the parametric complexity of schedules to minimize tardy tasks.
- \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
- On the complexity of Chamberlin-Courant on almost structured profiles
- Facility location problems: a parameterized view
- Fixed-parameter algorithms for maximum-profit facility location under matroid constraints
- Graph expansion and the unique games conjecture
- Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
- Parameterized Power Vertex Cover
- Graph Layout Problems Parameterized by Vertex Cover
- Polynomial algorithms in linear programming
- Chamberlin--Courant Rule with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time
- Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
- Reducibility among Combinatorial Problems
- Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
- Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
- Location Science
- Arc Routing
- Approximations for minimum and min-max vehicle routing problems
- Min-Max Graph Partitioning and Small Set Expansion
- A Functional Equation and its Application to Resource Allocation and Sequencing Problems
- Parameterized complexity of min-power asymmetric connectivity
