Cover Image

Approximation Schemes for k-Subset Sum Ratio and k-way Number Partitioning Ratio

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kanellopoulos, Sotiris, Mitropoulos, Giorgos, Antonopoulos, Antonis, Leonardos, Nikos, Pagourtzis, Aris, Pergaminelis, Christos, Petsalakis, Stavros, Tsitouras, Kanellos
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Finite Pinwheel Scheduling: the k-Visits Problem
by: Kanellopoulos, Sotiris, et al.
Published: (2025)

Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
by: Kanellopoulos, Sotiris, et al.
Published: (2026)

Beer Path Problems in Temporal Graphs
by: D'Ascenzo, Andrea, et al.
Published: (2025)

On the power of counting the total number of computation paths of NPTMs
by: Bakali, Eleni, et al.
Published: (2023)

Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM
by: Randolph, Tim, et al.
Published: (2024)

On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm
by: Zhong, Xianghui
Published: (2019)

EF(X) Orientations: A Parameterized Complexity Perspective
by: Kanellopoulos, Sotiris, et al.
Published: (2025)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
by: DeHaan, Ian, et al.
Published: (2024)

On the Min-Max Star Partitioning Number
by: Feldmann, Sarah, et al.
Published: (2024)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
by: Salas, Jesus
Published: (2025)

Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses
by: Chen, Lin, et al.
Published: (2025)

CRISP: Correlation-Resilient Indexing via Subspace Partitioning
by: Dimitropoulos, Dimitris, et al.
Published: (2026)

The Spanning Ratio of the Directed $Θ_6$-Graph is 5
by: Bose, Prosenjit, et al.
Published: (2026)

The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
by: van Renssen, Andrè, et al.
Published: (2022)

The Simplicial Geometry of Integer Partitions: An Exact $O(1)$ Formula via $A_{k-1}$ Root Systems
by: Bonelli, Antonio
Published: (2026)

On Minimum Maximal Distance-k Matchings
by: Kartynnik, Yury, et al.
Published: (2016)

On star-$k$-PCGs: Exploring class boundaries for small $k$ values
by: Monti, Angelo, et al.
Published: (2022)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

A note on the Ratio and Inertia Bounds for the $k$-Independence Number
by: Gao, Jun, et al.
Published: (2026)

On the satisfability of random k-Horn formulae
by: Istrate, Gabriel
Published: (2000)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
by: Dvořák, Pavel, et al.
Published: (2017)

Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration
by: Salas, Jesus
Published: (2025)

Almost Tight Additive Guarantees for $k$-Edge-Connectivity
by: Kumar, Nikhil, et al.
Published: (2025)

Golden Ratio Growth and Phase Transitions in Chromatic Counts of Circular Chord Graphs
by: Lopez-Bonilla, Rogelio N., et al.
Published: (2025)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
by: Heimann, Sophia, et al.
Published: (2024)

Eigenvalue Ratios for vibrating string equations with single-well densities
by: Hedhly, Jihed
Published: (2021)

Positional s-of-k games
by: Duchêne, Eric, et al.
Published: (2026)

Bounded Ratio Reinforcement Learning
by: Ao, Yunke, et al.
Published: (2026)

Improved seeding strategies for k-means and k-GMM
by: Carrière, Guillaume, et al.
Published: (2025)

Sums of $k$-bonacci Numbers
by: Parks, Harold R., et al.
Published: (2022)

Fairness in the k-Server Problem
by: Daneshvaramoli, Mohammadreza, et al.
Published: (2025)

Conflict-Free Colouring of Subsets
by: Jartoux, Bruno, et al.
Published: (2022)

Guarding Polyominoes Under $k$-Hop Visibility
by: Filtser, Omrit, et al.
Published: (2023)

Exploration of $k$-edge-deficient temporal graphs in linear time
by: Lahtin, Ivan, et al.
Published: (2026)

Improved Approximation Ratio for Strategyproof Facility Location on a Cycle
by: Rogowski, Krzysztof, et al.
Published: (2025)

An improved local search based algorithm for $k^-$-star partition
by: Gong, Mingyang, et al.
Published: (2025)

Beating Meet-in-the-Middle for Subset Balancing Problems
by: Randolph, Tim, et al.
Published: (2025)

Searching in trees with $k$-up-modular cost functions
by: Szyfelbein, Michał
Published: (2025)

The calculation of air filtration efficiency through the visual basic programming language
by: Kouropoulos, Giorgos
Published: (2014)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
by: Liao, Chao, et al.
Published: (2022)