標題: Titlebook: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques; 12th International W Irit Dinur,Klaus Jansen,José [打印本頁] 作者: mature 時間: 2025-3-21 16:27
書目名稱Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques影響因子(影響力)
書目名稱Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques影響因子(影響力)學科排名
書目名稱Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques網絡公開度
書目名稱Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques網絡公開度學科排名
書目名稱Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques被引頻次
書目名稱Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques被引頻次學科排名
書目名稱Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques年度引用
書目名稱Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques年度引用學科排名
書目名稱Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques讀者反饋
書目名稱Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques讀者反饋學科排名
作者: 車床 時間: 2025-3-22 00:19 作者: Lice692 時間: 2025-3-22 04:07
Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphspilers and have recently been proven NP-Hard. We provide the first constant approximations: a .-approximation for interval graphs and a .-approximation for chordal graphs. We extend our techniques to the problem of minimizing spillage in these graph types.作者: CHECK 時間: 2025-3-22 08:23 作者: 閹割 時間: 2025-3-22 09:39
Truthful Mechanisms via Greedy Iterative Packinge. A fundamental question is whether an .-approximation algorithm translates into an .-approximate truthful mechanism. It is well-known that plugging an .-approximation algorithm into the VCG technique may not yield a truthful mechanism. Thus, it is natural to investigate properties of approximation作者: myocardium 時間: 2025-3-22 13:35 作者: 哺乳動物 時間: 2025-3-22 17:52 作者: Entreaty 時間: 2025-3-23 00:18
New Hardness Results for Diophantine Approximationsion of this problem consists of a rational vector .?∈??., an error bound . and a denominator bound .?∈??.. One has to decide whether there exists an integer, called the.. with 1?≤?.?≤?. such that the distance of each number . ·.. to its nearest integer is bounded by .. Lagarias has shown that this 作者: 代替 時間: 2025-3-23 02:35
PASS Approximationtandard worst-case analysis. We circumvent such negative results by designing guarantees for classes of instances, parameterized according to properties of the optimal solution. We also make sure that our parameterized approximation, called . approximation, is the best possible. We show how to apply作者: 祖先 時間: 2025-3-23 06:32
Optimal Sherali-Adams Gaps from Pairwise Independenceted by . contains the support of a balanced pairwise independent distribution over the domain of the inputs, then such a problem on . variables cannot be approximated better than the trivial (random) approximation, even using Ω(.) levels of the Sherali-Adams LP hierarchy..It was recently shown [3] t作者: Perineum 時間: 2025-3-23 11:19
An Approximation Scheme for Terrain Guardinggorithm is a local search algorithm inspired by the recent results of Chan and Har-Peled [2] and Mustafa and Ray [15]. Our key contribution is to show the existence of a planar graph that appropriately relates the local and global optimum.作者: Pituitary-Gland 時間: 2025-3-23 16:03 作者: cyanosis 時間: 2025-3-23 20:07
Improved Inapproximability Results for Maximum ,-Colorable Subgraphrs so that a maximum fraction of edges are properly colored (i.e. their endpoints receive different colors). A random .-coloring properly colors an expected fraction . of edges. We prove that given a graph promised to be .-colorable, it is NP-hard to find a .-coloring that properly colors more than 作者: humectant 時間: 2025-3-23 23:42
Improved Absolute Approximation Ratios for Two-Dimensional Packing Problemsr bins or a strip of minimal height, respectively. All packings have to be non-overlapping and orthogonal, i.e., axis-parallel. Our algorithm for strip packing has an absolute approximation ratio of 1.9396 and is the first algorithm to break the approximation ratio of 2 which was established more th作者: conceal 時間: 2025-3-24 04:43 作者: ATRIA 時間: 2025-3-24 09:05
On Hardness of Pricing Items for Single-Minded Biddersers, each with a budget and an intention to buy a fixed subset of items. Given prices on the items, each buyer buys his subset of items, at the given prices, provided the total price of the subset is at most his budget. The objective of the seller is to determine the prices such that her total profi作者: 規(guī)范就好 時間: 2025-3-24 12:43
Real-Time Message Routing and Schedulingcheduling decisions. In order for messages to arrive on time, one has to determine a suitable (short) origin-destination path for each message and resolve conflicts between messages whose paths share a communication link of the network. We provide efficient routing strategies yielding origin-destina作者: 檢查 時間: 2025-3-24 17:45 作者: PANIC 時間: 2025-3-24 22:47 作者: 冰河期 時間: 2025-3-25 02:12
Structure Theory for p.m.p. Actions is to find a maximum cardinality set of element-disjoint trees such that each tree contains every terminal node. An . means a non-terminal node or an edge. (Thus, each non-terminal node and each edge must be in at most one of the trees.) We show that the problem is .-hard when there are only three 作者: fledged 時間: 2025-3-25 06:00 作者: ALT 時間: 2025-3-25 10:50
Structure Theory for p.m.p. Actionspilers and have recently been proven NP-Hard. We provide the first constant approximations: a .-approximation for interval graphs and a .-approximation for chordal graphs. We extend our techniques to the problem of minimizing spillage in these graph types.作者: 庇護 時間: 2025-3-25 14:35
Structure Theory for p.m.p. Actionse-capacitated graph .?=?(.,.) and . request pairs .., …, .., where each .. consists of a source-destination pair (..,..), a demand .. and a weight ... The goal is to find a maximum weight subset of requests that can be routed unsplittably in .. Most previous work on UFP has focused on the . case in 作者: indenture 時間: 2025-3-25 19:04
I. P. Cornfeld,S. V. Fomin,Ya. G. Sinaie. A fundamental question is whether an .-approximation algorithm translates into an .-approximate truthful mechanism. It is well-known that plugging an .-approximation algorithm into the VCG technique may not yield a truthful mechanism. Thus, it is natural to investigate properties of approximation作者: 過去分詞 時間: 2025-3-25 20:58 作者: infringe 時間: 2025-3-26 00:22 作者: 北極人 時間: 2025-3-26 08:16
Smooth Dynamical Systems on Smooth Manifoldssion of this problem consists of a rational vector .?∈??., an error bound . and a denominator bound .?∈??.. One has to decide whether there exists an integer, called the.. with 1?≤?.?≤?. such that the distance of each number . ·.. to its nearest integer is bounded by .. Lagarias has shown that this 作者: Tailor 時間: 2025-3-26 08:45
I. P. Cornfeld,S. V. Fomin,Ya. G. Sinaitandard worst-case analysis. We circumvent such negative results by designing guarantees for classes of instances, parameterized according to properties of the optimal solution. We also make sure that our parameterized approximation, called . approximation, is the best possible. We show how to apply作者: outset 時間: 2025-3-26 12:37 作者: GLOSS 時間: 2025-3-26 20:52 作者: doxazosin 時間: 2025-3-27 00:29
Conditional Measures and Algebras,job has a specified profit, and we are no longer required to process all jobs? Instead, we can schedule any subset of jobs whose total profit is at least a (hard) target profit requirement, while still trying to approximately minimize the objective function..We refer to this class of problems as .. 作者: 招惹 時間: 2025-3-27 02:26
https://doi.org/10.1007/978-3-642-70335-5rs so that a maximum fraction of edges are properly colored (i.e. their endpoints receive different colors). A random .-coloring properly colors an expected fraction . of edges. We prove that given a graph promised to be .-colorable, it is NP-hard to find a .-coloring that properly colors more than 作者: CESS 時間: 2025-3-27 07:49
https://doi.org/10.1007/978-3-642-70335-5r bins or a strip of minimal height, respectively. All packings have to be non-overlapping and orthogonal, i.e., axis-parallel. Our algorithm for strip packing has an absolute approximation ratio of 1.9396 and is the first algorithm to break the approximation ratio of 2 which was established more th作者: Stagger 時間: 2025-3-27 10:34 作者: 彈藥 時間: 2025-3-27 17:07
Ergodic Theory and Dynamical Systemsers, each with a budget and an intention to buy a fixed subset of items. Given prices on the items, each buyer buys his subset of items, at the given prices, provided the total price of the subset is at most his budget. The objective of the seller is to determine the prices such that her total profi作者: Nonconformist 時間: 2025-3-27 19:40
Measurable Partitions and ,-Algebrascheduling decisions. In order for messages to arrive on time, one has to determine a suitable (short) origin-destination path for each message and resolve conflicts between messages whose paths share a communication link of the network. We provide efficient routing strategies yielding origin-destina作者: 暴露他抗議 時間: 2025-3-28 00:52 作者: groggy 時間: 2025-3-28 04:27 作者: 通情達理 時間: 2025-3-28 09:31 作者: Rebate 時間: 2025-3-28 13:15
978-3-642-03684-2Springer-Verlag Berlin Heidelberg 2009作者: B-cell 時間: 2025-3-28 16:31
Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphspilers and have recently been proven NP-Hard. We provide the first constant approximations: a .-approximation for interval graphs and a .-approximation for chordal graphs. We extend our techniques to the problem of minimizing spillage in these graph types.作者: Detoxification 時間: 2025-3-28 21:20
An Approximation Scheme for Terrain Guardinggorithm is a local search algorithm inspired by the recent results of Chan and Har-Peled [2] and Mustafa and Ray [15]. Our key contribution is to show the existence of a planar graph that appropriately relates the local and global optimum.作者: maladorit 時間: 2025-3-29 01:09 作者: blister 時間: 2025-3-29 05:53
0302-9743 Overview: 978-3-642-03684-2978-3-642-03685-9Series ISSN 0302-9743 Series E-ISSN 1611-3349 作者: DOTE 時間: 2025-3-29 07:23 作者: 深陷 時間: 2025-3-29 14:56
Invariant Measures for Continuous Maps,gorithm is a local search algorithm inspired by the recent results of Chan and Har-Peled [2] and Mustafa and Ray [15]. Our key contribution is to show the existence of a planar graph that appropriately relates the local and global optimum.作者: 鬼魂 時間: 2025-3-29 15:44
Lecture Notes in Computer Sciencehttp://image.papertrans.cn/b/image/160461.jpg作者: Adrenal-Glands 時間: 2025-3-29 20:57 作者: Nebulous 時間: 2025-3-30 02:17
Structure Theory for p.m.p. Actionsaxation for UFP on paths that has an integrality gap of .(log..); previously there was no relaxation with .(.) gap. We also consider UFP in general graphs and CPIPs without the no-bottleneck assumption and obtain new and useful results.作者: Perigee 時間: 2025-3-30 05:16
I. P. Cornfeld,S. V. Fomin,Ya. G. Sinai loser-independent algorithms can be employed as sub-procedures in a greedy iterative packing approach while preserving monotonicity. A greedy iterative approach provides a good approximation in the context of maximizing a non-decreasing submodular function subject to independence constraints. Our f作者: Magisterial 時間: 2025-3-30 09:59
Smooth Dynamical Systems on Smooth Manifoldsed version of Diophantine approximation is also hard to approximate. Furthermore we prove that the . problem with arbitrary capacities is NP-hard. This solves an open problem raised by Conforti, Di?Summa and Wolsey.作者: Commentary 時間: 2025-3-30 13:25
I. P. Cornfeld,S. V. Fomin,Ya. G. Sinairoblems is not optimal in our framework. We design a new LP relaxation and show that this LP relaxation coupled with a new randomized rounding technique is optimal in our framework..In passing, we note that our results strictly improve over previous results of Kleinberg, Papadimitriou and Raghavan [作者: 樂意 時間: 2025-3-30 19:29
Ergodic Theory and Dynamical Systemsn integrality gap of 4, even in this special case. Then we prove that the problem is NP-hard to approximate within a factor of 2 assuming the Unique Games Conjecture; and it is unconditionally NP-hard to approximate within a factor 17/16. Finally, we extend the APX-hardness of the problem to the spe作者: VAN 時間: 2025-3-30 20:41
Ergodic Theory and Dynamical Systemsal., FOCS 2006] and [Chekuri et al., SODA 2007]. This technique seems quite robust and was already used in order to improve the ratio of Buy-at-bulk with protection (Antonakopoulos et al FOCS 2007) from log.. to log... See ?..We also consider the . (.) problem which is closely related to .: given a 作者: Endometrium 時間: 2025-3-31 04:21 作者: kyphoplasty 時間: 2025-3-31 07:27 作者: MOAN 時間: 2025-3-31 10:43 作者: 遭遇 時間: 2025-3-31 14:24
New Hardness Results for Diophantine Approximationed version of Diophantine approximation is also hard to approximate. Furthermore we prove that the . problem with arbitrary capacities is NP-hard. This solves an open problem raised by Conforti, Di?Summa and Wolsey.作者: ATP861 時間: 2025-3-31 18:48
PASS Approximationroblems is not optimal in our framework. We design a new LP relaxation and show that this LP relaxation coupled with a new randomized rounding technique is optimal in our framework..In passing, we note that our results strictly improve over previous results of Kleinberg, Papadimitriou and Raghavan [作者: MAUVE 時間: 2025-4-1 01:29 作者: Thrombolysis 時間: 2025-4-1 04:10
Approximating Some Network Design Problems with Node Costsal., FOCS 2006] and [Chekuri et al., SODA 2007]. This technique seems quite robust and was already used in order to improve the ratio of Buy-at-bulk with protection (Antonakopoulos et al FOCS 2007) from log.. to log... See ?..We also consider the . (.) problem which is closely related to .: given a 作者: Reservation 時間: 2025-4-1 09:57
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques12th International W
