An approximation algorithm for the <Emphasis Type="Italic">k</Emphasis>-level capacitated facility location problem

We consider the k-level capacitated facility location problem (k-CFLP), which is a natural variant of the classical facility location problem and has applications in supply chain management. We obtain the first (combinatorial) approximation algorithm with a performance factor of \(k+2+\sqrt{k^{2}+2k+5}+\varepsilon\) (ε>0) for this problem.     

An approximation algorithm for the uniform capacitated k-means problem

Journal of Combinatorial Optimization - In this paper, we consider the uniform capacitated k-means problem (UC-k-means), an extension of the classical k-means problem (k-means) in machine learning....     

论对债权执行的边界——兼评《民事强制执行法(草案)》中的债权执行条款

对债权执行边界的确定,关乎执行债务人责任财产的认定与第三人的利益保障,对于确保执行正当性具有重要意义。在我国民事强制执行法典编纂之际,如何界定债权执行客体的应然范围,是推进债权执行制度体系化建构的关键问题。债权执行边界的生成机理包括责任财产理论、执行标的有限原则以及利益平衡原理。依据责任财产理论,作为执行客体的债权须具备经济价值、独立性与可让与性,且该债权归属于执行债务人所有。基于维护公益与尊重人权的需要,对债权的执行应当遵循执行标的有限原则,不得强制执行实体法上禁止让与的债权与程序法上禁止执行的债权。而利益平衡原理则要求执行机关适度平衡多元主体之间的权益保护,避免对债务人和第三人造成过重的负担。在宏观上,应当将债权执行划分为“基本型”和“占有型”,并在此基础上对其客体形态分别予以重构。“基本型”用于实现给付金钱之执行名义,其执行客体应当涵盖非到期债权与非金钱债权。唯将来债权的扣押须受一定限制,应结合作为债权基础的法律关系、将来债权发生的可能性、主体的特定化予以斟酌。在继续性给付债权扣押效力范围的判断上,应当秉持债权基础关系的单一说,同时对立法草案的相关条文予以调整。“占有型”用于实现交付物之执行名义,其适用场域应限定为第三人对执行债务人负有交付义务的情形。若第三人属于当事人的继受人、为当事人或者继受人利益而占有标的物者,不得适用债权执行方法。较域外而言,由于我国对第三人采用径为执行方式,阻却“占有型”债权执行的事由亦呈现特殊性。     

An approximation algorithm for <Emphasis Type="Italic">k</Emphasis>-facility location problem with linear penalties using local search scheme

In this paper, we consider an extension of the classical facility location problem, namely k-facility location problem with linear penalties. In contrast to the classical facility location problem, this problem opens no more than k facilities and pays a penalty cost for any non-served client. We present a local search algorithm for this problem with a similar but more technical analysis due to the extra penalty cost, compared to that in Zhang (Theoretical Computer Science 384:126–135, 2007). We show that the approximation ratio of the local search algorithm is \(2 + 1/p + \sqrt{3+ 2/p+ 1/p^2} + \epsilon \), where \(p \in {\mathbb {Z}}_+\) is a parameter of the algorithm and \(\epsilon >0\) is a positive number.     

A local search approximation algorithm for the uniform capacitated <Emphasis Type="Italic">k</Emphasis>-facility location problem

In the uniform capacitated k-facility location problem (UC-k-FLP), we are given a set of facilities and a set of clients. Every client has a demand. Every facility have an opening cost and an uniform capacity. For each client–facility pair, there is an unit service cost to serve the client with unit demand by the facility. The total demands served by a facility cannot exceed the uniform capacity. We want to open at most k facilities to serve all the demands of the clients without violating the capacity constraint such that the total opening and serving cost is minimized. The main contribution of this work is to present the first combinatorial bi-criteria approximation algorithm for the UC-k-FLP by violating the cardinality constraint.     

A local search approximation algorithm for a squared metric <Emphasis Type="Italic">k</Emphasis>-facility location problem

We consider a scheduling problem where machines need to be rented from the cloud in order to process jobs. There are two types of machines available which can be rented for machine-type dependent prices and for arbitrary durations. However, a machine-type dependent setup time is required before a machine is available for processing. Jobs arrive online over time, have deadlines and machine-type dependent sizes. The objective is to rent machines and schedule jobs so as to meet all deadlines while minimizing the rental cost. As we observe the slack of jobs to have a fundamental influence on the competitiveness, we parameterize instances by their (minimum) slack. An instance is called to have a slack of \(\beta \) if, for all jobs, the difference between the job’s release time and the latest point in time at which it needs to be started is at least \(\beta \). While for \(\beta < s\) no finite competitiveness is possible, our main result is an online algorithm for \(\beta = (1+\varepsilon )s\) with Open image in new window , where s denotes the largest setup time. Its competitiveness only depends on \(\varepsilon \) and the cost ratio of the machine types and is proven to be optimal up to a factor of Open image in new window .     

当代“人学”的支点:人的有意识的自由自觉的类特性——读马克思《1844年经济学哲学手稿》之感悟

以卡尔·马克思青年时期的《1844年经济学哲学手稿》等著作为文本根据,省悟出《手稿》将人的类本性抽象并具体为"有意识的、自由自觉的、自为自愿的、感觉激情的生命活动",是当代"人学"的最高视角。     

"以人为本"和"以物为本"的哲学性质及现实意义

本文以我党近年提出来的"以人为本"的新发展观为纲领,从卡尔·马克思的"人的自由全面发展观"和"以人为本"的"实践人道主义"哲学的高度,讨论了"以人为本"的哲学本性.同时批判了以"拜物主义"为"教义"的"以物为本"的历史观,揭露了这种历史观对当下我国的社会发展的极其严重的危害.文章充分肯定了卡尔·马克思的"以人为本"的"实践人本主义"对我国和人类的发展的重要指导意义,进而呼吁"马克思不能丢".     

无约束优化DFP算法的全局收敛性

讨论了无约束优化问题的ＤＦＰ算法的全局收敛性．在适当的条件下，证明了对一致凸目标函数，在非精确线搜索下ＤＦＰ算法具有全局收敛性     

对卡尔·马克思"共产主义"理想的解读

对于资本社会后的人类理想社会,马克思从社会的不同层面创意出不同的蓝图.文章对"共产主义"和"自由人联合体"这两大创意进行了比较研究,并从中解读出两者的"和而不同",划界了"科学共产主义"和"哲学共产主义".