Anthropoid
发表于 2025-3-30 10:24:15
Fixed-Order Scheduling on Parallel Machines,of . identical machines in order to minimize the sum of weighted completion times. The twist is that for machine the jobs assigned to it must obey the order of the input sequence, as is the case in multi-server queuing systems. We establish a constant factor approximation algorithm for this (strongl
coagulate
发表于 2025-3-30 16:16:39
Online Submodular Maximization: Beating 1/2 Made Simple,perspectives. In particular, it has been studied in a natural online setting in which items arrive one-by-one and should be allocated irrevocably upon arrival. In this setting, it is well known that the greedy algorithm achieves a competitive ratio of ., and recently Kapralov . [.] showed that this
Sinus-Rhythm
发表于 2025-3-30 18:36:57
Improving the Integrality Gap for Multiway Cut,partition the node set of the graph into . non-empty parts each containing exactly one terminal so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for . is APX-hard. For arbitrary ., the best-known approximation factor is 1.2965 due to Sharma and Vond
落叶剂
发表于 2025-3-30 21:34:51
-sparsity Approximation Bounds for Packing Integer Programs, . which is at least 1. Previous work by Bansal et al. [.] obtained an .-approximation ratio where . is the maximum number of nonzeroes in any column of . (in other words the .-column sparsity of .). They raised the question of obtaining approximation ratios based on the .-column sparsity of . (deno
Obsessed
发表于 2025-3-31 04:07:32
A General Framework for Handling Commitment in Online Throughput Maximization,mine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least . times its processing time, for some .. We quantif
罗盘
发表于 2025-3-31 06:42:49
http://reply.papertrans.cn/47/4683/468242/468242_56.png
ROOF
发表于 2025-3-31 10:21:02
,On Friedmann’s Subexponential Lower Bound for Zadeh’s Pivot Rule, Zadeh’s pivot rule had long been a promising candidate, before Friedmann (IPCO, 2011) presented a subexponential instance, based on a close relation to policy iteration algorithms for Markov decision processes (MDPs). We investigate Friedmann’s lower bound construction and exhibit three flaws in hi
VEN
发表于 2025-3-31 16:24:12
http://reply.papertrans.cn/47/4683/468242/468242_58.png
等待
发表于 2025-3-31 19:36:55
Integer Programming and Incidence Treedepth,ucture of its constraint matrix on the other side. To that end, integer linear programming is fixed-parameter tractable with respect to the primal (or dual) treedepth of the Gaifman graph of its constraint matrix and the largest coefficient (in absolute value). Motivated by this, Koutecký, Levin, an
暴行
发表于 2025-4-1 01:31:32
A Bundle Approach for SDPs with Exact Subgraph Constraints,al NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrang