ITCH
发表于 2025-3-30 12:13:14
Integrality Gaps of Integer Knapsack Problems,We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a “typical” knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario.
hauteur
发表于 2025-3-30 14:04:53
978-3-319-59249-7Springer International Publishing AG 2017
打折
发表于 2025-3-30 18:22:35
http://reply.papertrans.cn/47/4683/468256/468256_53.png
甜瓜
发表于 2025-3-30 22:26:55
https://doi.org/10.1007/978-3-319-59250-3Approximation theory; Combinatorial optimization; Computational results; Integer programming; Linear pro
Fallibility
发表于 2025-3-31 01:48:34
,An Improved Integrality Gap for the Călinescu-Karloff-Rabani Relaxation for Multiway Cut,tance has an integrality ratio of ., for every constant .. For every ., this improves upon a long-standing lower bound of . by Freund and Karloff [.]. Due to the result by Manokaran et al. [.], our integrality gap also implies Unique Games hardness of approximating Multiway Cut of the same ratio.
Impugn
发表于 2025-3-31 08:20:51
http://reply.papertrans.cn/47/4683/468256/468256_56.png
burnish
发表于 2025-3-31 12:30:58
On Scheduling Coflows,-approximation and a randomized .-approximation algorithm. In this paper, we give a combinatorial algorithm that yields a deterministic 5-approximation algorithm with release times, and a deterministic 4-approximation for the case without release time.
Arteriography
发表于 2025-3-31 16:14:29
http://reply.papertrans.cn/47/4683/468256/468256_58.png
MOAN
发表于 2025-3-31 19:46:45
Mixed-Integer Linear Representability, Disjunctions, and Variable Elimination,vered by the Williams-Hooker scheme. Second, disjunctions of Chvátal systems can give sets that are . projections of mixed-integer linear sets; so the Williams-Hooker approach does not give an exact characterization of MILP representability.
ERUPT
发表于 2025-4-1 00:08:47
Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in ,(1) Amortized Updaf .. Our result can be generalized to give a fully dynamic .-approximation algorithm with . amortized update time for the hypergraph vertex cover and fractional matching problems, where every hyperedge has at most . vertices.