Cover Image

Non-convex relaxation and 1/2-approximation algorithm for the chance-constrained binary knapsack problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kim, Junyoung, Lee, Kyungsik
Format:	Preprint
Published:	2024
Subjects:	Optimization and Control Discrete Mathematics Combinatorics 90C15, 90C27, 90C59
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

A Computational Search for Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
by: Au, Yu Hin, et al.
Published: (2025)

The exact subgraph hierarchy and its vertex-transitive variant for the stable set problem for Paley graphs
by: Gaar, Elisabeth, et al.
Published: (2024)

Stable Set Polytopes with Rank $|V(G)|/3$ for the Lovász--Schrijver SDP Operator
by: Au, Yu Hin, et al.
Published: (2025)

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

Solving Combinatorial Pricing Problems using Embedded Dynamic Programming Models
by: Bui, Quang Minh, et al.
Published: (2024)

On different Versions of the Exact Subgraph Hierarchy for the Stable Set Problem
by: Gaar, Elisabeth
Published: (2020)

Strong SDP based bounds on the cutwidth of a graph
by: Gaar, Elisabeth, et al.
Published: (2023)

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

On the redundancy of transitivity constraints in the clique partitioning problem
by: Sukegawa, Noriyoshi
Published: (2026)

Computing All Shortest Passenger Routes with a Tropical Dijkstra Algorithm
by: Masing, Berenike, et al.
Published: (2024)

Benders decomposition algorithms for minimizing the spread of harmful contagions in networks
by: Tanınmış, Kübra, et al.
Published: (2023)

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

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

Convex quadratic sets and the complexity of mixed integer convex quadratic programming
by: Del Pia, Alberto
Published: (2023)

Rescue Craft Allocation in Tidal Waters of the North and Baltic Sea
by: Mucke, Tom, et al.
Published: (2024)

Almost Orthogonal Arrays: Search Three Ways
by: Martínez, Luis, et al.
Published: (2024)

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)

Augmentation Algorithms for Integer Programs with Total Variation-like Regularization
by: Yang, Dominic, et al.
Published: (2025)

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

A solution procedure for minimizing total completion time in a parallel-batching environment
by: Alfieri, Arianna, et al.
Published: (2020)

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

Applying a Random-Key Optimizer on Mixed Integer Programs
by: Chaves, Antonio A., et al.
Published: (2026)

On exactness of SDP relaxation for the maximum cut problem
by: Bhardwaj, Avinash, et al.
Published: (2025)

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

Semidefinite approximations for bicliques and biindependent pairs
by: Laurent, Monique, et al.
Published: (2023)

Simulation-Optimization Approaches for the Network Immunization Problem with Quarantining
by: Hoogervorst, Rowan, et al.
Published: (2024)

A Multi-Reference Relaxation Enforced Neighborhood Search Heuristic in SCIP
by: Bolusani, Suresh, et al.
Published: (2024)

IP Models for Minimum Zero Forcing Sets, Forts, and Related Graph Parameters
by: Cameron, Thomas R., et al.
Published: (2025)

Randomized quasi-Monte Carlo methods for risk-averse stochastic optimization
by: Melnikov, Olena, et al.
Published: (2024)

Bundle methods with quadratic cuts for deterministic and stochastic strongly convex optimization problems
by: Guigues, Vincent, et al.
Published: (2017)

Generalizations of Total Dual Integrality
by: Guenin, Bertrand, et al.
Published: (2025)

A Note on Piecewise Affine Decision Rules for Robust, Stochastic, and Data-Driven Optimization
by: Thomä, Simon, et al.
Published: (2024)

The rainbow covering number of clean tangled clutters
by: Abdi, Ahmad, et al.
Published: (2025)

Extending the definition of set tolerances
by: Jäger, Gerold, et al.
Published: (2024)

On feasibility cuts for chance-constrained multicommodity network design problems
by: Wouda, Niels A., et al.
Published: (2024)

Polyhedral approximation of spectrahedral shadows via homogenization
by: Dörfler, Daniel, et al.
Published: (2023)

New Formulation for Coloring Circle Graphs and its Application to Capacitated Stowage Stack Minimization
by: Tanaka, Masato, et al.
Published: (2021)

Competing for the most profitable tour: The orienteering interdiction game
by: Álvarez-Miranda, Eduardo, et al.
Published: (2024)

Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem
by: Vodeb, Jaka, et al.
Published: (2024)