Cover Image

An overview of some single machine scheduling problems: polynomial algorithms, complexity and approximability

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Vakhania, Nodari, Werner, Frank, Ramírez-Fuentes, Kevin Johedan, Pacheco-Valencia, Víctor
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms 90B35 (Primary), 90C59 (Secondary)
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An online joint replenishment problem combined with single machine scheduling
by: Györgyi, Péter, et al.
Published: (2022)

Compact enumeration for scheduling one machine
by: Vakhania, Nodari
Published: (2021)

Troika algorithm: approximate optimization for accurate clique partitioning and clustering of weighted networks
by: Aref, Samin, et al.
Published: (2025)

The Bounded Acceleration Shortest Path problem: complexity and solution algorithms
by: Ardizzoni, Stefano, et al.
Published: (2021)

A Speed-up for Helsgaun's TSP Heuristic by Relaxing the Positive Gain Criterion
by: Ammann, Sabrina C. L., et al.
Published: (2024)

Reducing Dominating Sets in Graphs
by: Inza, Ernesto Parra, et al.
Published: (2024)

Metaheuristic algorithms for the induced P-median problem with upgrades
by: Salazar, Sergio, et al.
Published: (2026)

Non-convex relaxation and 1/2-approximation algorithm for the chance-constrained binary knapsack problem
by: Kim, Junyoung, et al.
Published: (2024)

Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
by: Aref, Samin, et al.
Published: (2022)

Heuristic algorithms for the stochastic critical node detection problem
by: Bayarsaikhan, Tuguldur, et al.
Published: (2025)

An efficient recursive decomposition algorithm for undirected graphs
by: Heng, Pei, et al.
Published: (2026)

A diving heuristic for mixed-integer problems with unbounded semi-continuous variables
by: Halbig, Katrin, et al.
Published: (2024)

Solving Hard Instances from Knapsack and Bounded Knapsack Problems: A new state-of-the-art solver
by: da Silva, Renan F. F., et al.
Published: (2026)

Polynomial and Pseudopolynomial Algorithms for Two Classes of Bin Packing Instances
by: da Silva, Renan Fernando Franco, et al.
Published: (2026)

Two-stage heuristic algorithm for a new variant of the multi-compartment vehicle routing problem with stochastic demands
by: Gonçalves-Dosantos, Juan Carlos, et al.
Published: (2024)

A study of column generation embedded in scalarization methods for the bi-objective cutting stock problem
by: Borges, Jennifer C., et al.
Published: (2026)

A priority-driven constructive heuristic for assigning and scheduling spontaneous volunteers in disaster response
by: Sperling, Martina
Published: (2026)

An ODE approach to multiple choice polynomial programming
by: Shao, Sihong, et al.
Published: (2022)

On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers"
by: Diaby, Moustapha, et al.
Published: (2023)

An improved approximation algorithm for k-Median
by: Young, Neal E.
Published: (2025)

Column-generation for a two-dimensional multi-criteria bin-packing problem
by: Groschke, Christof, et al.
Published: (2025)

The Competition Complexity of Prophet Inequalities
by: Brustle, Johannes, et al.
Published: (2024)

Optimal routing and transmission strategies for UAV reconnaissance missions with detection threats
by: Badenbroek, Riley, et al.
Published: (2024)

Implicit Decision Diagrams
by: Rudich, Isaac, et al.
Published: (2026)

Assignment-Routing Optimization with Cutting-Plane Subtour Elimination: Solver and Benchmark Dataset
by: Yuan, Qilong
Published: (2025)

A Benson-Type Algorithm for Bounded Convex Vector Optimization Problems with Vertex Selection
by: Dörfler, Daniel, et al.
Published: (2020)

Finding Short Paths on Simple Polytopes
by: Black, Alexander E., et al.
Published: (2026)

Perpertual Coupled Simulated Annealing for Continuous Optimization
by: Gonçalves-e-Silva, Kayo, et al.
Published: (2018)

Convergence analysis of a primal-dual optimization-by-continuation algorithm
by: Loris, Ignace, et al.
Published: (2023)

An $n^{O(\log\log n)}$ time approximation scheme for capacitated VRP in the Euclidean plane
by: Sitters, René
Published: (2025)

Approximation algorithms for the prize-collecting rural postman problem
by: Li, Hong, et al.
Published: (2026)

Fix-and-Propagate Heuristics Using Low-Precision First-Order LP Solutions for Large-Scale Mixed-Integer Linear Optimization
by: Kempke, Nils-Christian, et al.
Published: (2025)

Strongly-polynomial time and validation analysis of policy gradient methods
by: Ju, Caleb, et al.
Published: (2024)

Projection, Degeneracy, and Singularity Degree for Spectrahedra
by: Im, Haesol, et al.
Published: (2024)

A Solution Concept for Convex Vector Optimization Problems based on a User-defined Region of Interest
by: Dörfler, Daniel, et al.
Published: (2026)

Globally Solving Concave Quadratic Programs via Doubly Nonnegative Relaxation
by: Qu, Zheng, et al.
Published: (2023)

A Canceling Heuristic for the Directed Traveling Salesman Problem
by: Borgwardt, Steffen, et al.
Published: (2026)

Efficient Tree Generation for Globally Optimal Decisions under Probabilistic Outcomes
by: Ozturk, Berk, et al.
Published: (2025)

Online Rack Placement in Large-Scale Data Centers: Online Sampling Optimization and Deployment
by: Baxi, Saumil, et al.
Published: (2025)

Coach Reservation for Groups Requests
by: Cardonha, Carlos H., et al.
Published: (2024)