標題: Titlebook: Automata, Languages, and Programming; 39th International C Artur Czumaj,Kurt Mehlhorn,Roger Wattenhofer Conference proceedings 2012 Springe [打印本頁] 作者: GUST 時間: 2025-3-21 16:19
書目名稱Automata, Languages, and Programming影響因子(影響力)
書目名稱Automata, Languages, and Programming影響因子(影響力)學(xué)科排名
書目名稱Automata, Languages, and Programming網(wǎng)絡(luò)公開度
書目名稱Automata, Languages, and Programming網(wǎng)絡(luò)公開度學(xué)科排名
書目名稱Automata, Languages, and Programming被引頻次
書目名稱Automata, Languages, and Programming被引頻次學(xué)科排名
書目名稱Automata, Languages, and Programming年度引用
書目名稱Automata, Languages, and Programming年度引用學(xué)科排名
書目名稱Automata, Languages, and Programming讀者反饋
書目名稱Automata, Languages, and Programming讀者反饋學(xué)科排名
作者: ALT 時間: 2025-3-21 23:15 作者: 采納 時間: 2025-3-22 04:28
Quantum Strategies Are Better Than Classical in Almost Any XOR Game More precisely, for large ., the entangled value of a random 2-player XOR game with . questions to every player is at least 1.21... times the classical value, for 1???.(1) fraction of all 2-player XOR games.作者: 會議 時間: 2025-3-22 06:07 作者: 折磨 時間: 2025-3-22 12:38 作者: 代理人 時間: 2025-3-22 16:25 作者: MEN 時間: 2025-3-22 20:04
Secretary Problems with Convex Costs objective. Requests are presented online in random order, and each request possesses an adversarial value and an adversarial size. The online algorithm must make an irrevocable accept/reject decision as soon as it sees each request. The “profit” of a set of accepted requests is its total value minu作者: accrete 時間: 2025-3-22 21:14 作者: 強制令 時間: 2025-3-23 05:15 作者: hematuria 時間: 2025-3-23 09:16
On Quadratic Programming with a Ratio Objectivetorial optimization problems, and assuming the Unique Games conjecture, Semidefinite Programming (SDP) techniques give optimal approximation algorithms. We extend this body of work by initiating the study of Quadratic Programming problems where the variables take values in the domain {???1,0,1}. The作者: clarify 時間: 2025-3-23 12:30 作者: Asseverate 時間: 2025-3-23 15:02 作者: calumniate 時間: 2025-3-23 20:17
Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraintsatroid is defined. The goal is to incrementally choose a subset that remains independent in the matroid over time. At each time, a new weighted rank function of a different matroid (one per time) over the same elements is presented; the algorithm can add a few elements to the incrementally construct作者: Sinus-Rhythm 時間: 2025-3-24 01:42 作者: Buttress 時間: 2025-3-24 03:04 作者: 取消 時間: 2025-3-24 10:18
Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree, if for any subset .???. with |.|?≤?., it holds that ..(., .)?≤?. ·.(., .), for any pair of ., .?∈?.???...For any doubling metric, we give a basic construction of .-VFTS with stretch arbitrarily close to 1 that has optimal .(.) edges. In addition, we also consider bounded hop-diameter, which is stu作者: 不透氣 時間: 2025-3-24 13:55 作者: POWER 時間: 2025-3-24 15:21 作者: Pelvic-Floor 時間: 2025-3-24 19:07 作者: Corroborate 時間: 2025-3-25 02:10
Efficient Submodular Function Maximization under Linear Packing Constraints when the number of constraints is constant or when the width of the constraints is sufficiently large. This motivates us to study the large width setting, trying to determine its exact approximability. We develop an algorithm that has an approximation ratio of (1???.)(1???1/.) when .?=?Ω(ln . / ..)作者: genesis 時間: 2025-3-25 04:32
Secretary Problems with Convex Costsunder various feasibility constraints and present online algorithms with competitive ratios only a constant factor worse than those known in the absence of costs for the same feasibility constraints. We also consider a multi-dimensional version of the problem that generalizes multi-dimensional knaps作者: FAST 時間: 2025-3-25 08:23
Nearly Simultaneously Resettable Black-Box Zero Knowledgeumber of times. The main contribution of our construction is that the round complexity is independent of the above bound. To achieve our result, we construct a constant-round nearly simultaneously resettable coin-flipping protocol that we believe is of independent interest.作者: 親愛 時間: 2025-3-25 14:40 作者: Chagrin 時間: 2025-3-25 19:22
Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraintsime. This problem is a natural extension of two well-studied streams of earlier work: the first is on online set cover algorithms (in particular for the max coverage version) while the second is on approximately maximizing submodular functions under a matroid constraint..In this paper, we present th作者: Harbor 時間: 2025-3-25 20:14 作者: 阻礙 時間: 2025-3-26 03:52 作者: bronchiole 時間: 2025-3-26 06:33 作者: ALIAS 時間: 2025-3-26 09:24 作者: PANIC 時間: 2025-3-26 12:40
https://doi.org/10.1007/978-3-658-01870-2orithms and evidence for the hardness of approximating these problems..We consider an SDP relaxation obtained by adding constraints to the natural eigenvalue (or SDP) relaxation for this problem. Using this, we obtain an . approximation algorithm for QP-ratio. We also give a . approximation for bipa作者: 預(yù)感 時間: 2025-3-26 19:03 作者: 幻想 時間: 2025-3-26 22:48
https://doi.org/10.1007/978-3-8350-5553-7.-median..We also give a 34-approximation for the knapsack median problem, which greatly improves the approximation constant in [13]. Using the same technique, we also give a 9-approximation for matroid median problem introduced in [11], improving on their 16-approximation.作者: 使困惑 時間: 2025-3-27 03:11
Efficient Sampling Methods for Discrete Distributionsoth problems, we present on two different classes of inputs – sorted and general probabilities – efficient preprocessing algorithms that allow for asymptotically optimal querying, and prove almost matching lower bounds for their complexity.作者: Pander 時間: 2025-3-27 07:59
Improved LP-Rounding Approximation Algorithm for ,-level Uncapacitated Facility Locationding builds upon the technique of iteratively rounding fractional solutions on trees (Garg, Konjevod, and Ravi SODA’98) originally used for the group Steiner tree problem..We improve the approximation ratio for .-UFL for all .?≥?3, in particular we obtain the ratio equal 2.02, 2.14, and 2.24 for .?=?3,4, and 5.作者: 很像弓] 時間: 2025-3-27 12:55 作者: Bridle 時間: 2025-3-27 14:06
0302-9743 refereed proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP 2012, held in Warwick, UK, in July 2012. The total of 123 revised full papers presented in this volume were carefully reviewed and selected from 432 submissions. They are organized in three track作者: amygdala 時間: 2025-3-27 18:03
Conference proceedings 2012lected from 432 submissions. They are organized in three tracks focussing on algorithms, complexity and games; logic, semantics, automata and theory of programming; and foundations of networked computation.作者: 惡臭 時間: 2025-3-27 23:19 作者: 受辱 時間: 2025-3-28 05:26 作者: 返老還童 時間: 2025-3-28 08:27
Kostensenkung bei indirekten Materialien,gree distributions which trades accuracy for tractability. In particular, our bounds only require the solution of a 1-dimensional optimization problem (which typically turns out to be very easy) and as such can be used to compute explicit rigorous unsatisfiability bounds.作者: 混沌 時間: 2025-3-28 11:44 作者: BARGE 時間: 2025-3-28 15:21
,Abwicklungs- und Zahlungsmodalit?ten,l solution to change in a small fraction of the points after perturbation. We also provide positive results for min-sum clustering which is a generally much harder objective than .-median (and also non-center-based). Our algorithms are based on new linkage criteria that may be of independent interest.作者: Bridle 時間: 2025-3-28 21:00 作者: 水汽 時間: 2025-3-29 02:31 作者: 秘傳 時間: 2025-3-29 04:22 作者: Badger 時間: 2025-3-29 08:41 作者: 無節(jié)奏 時間: 2025-3-29 11:33
Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Methodgree distributions which trades accuracy for tractability. In particular, our bounds only require the solution of a 1-dimensional optimization problem (which typically turns out to be very easy) and as such can be used to compute explicit rigorous unsatisfiability bounds.作者: 友好 時間: 2025-3-29 18:52 作者: Atheroma 時間: 2025-3-29 21:52 作者: CHOP 時間: 2025-3-30 02:31
Complexity of Complexity and Maximal Plain versus Prefix-Free Kolmogorov Complexityesult. We also generalize it by showing that for some . and for all . there are strings . of length . with .???.(.)?≤?., and .?+?.(.)???.(.)?≥?.(.(.)|.)???3.( .(.(.)|.) |.)???. . This is very close to the upperbound .(.(.)|.)?+?.(1) proved by Solovay.作者: 漸變 時間: 2025-3-30 04:46 作者: 一起平行 時間: 2025-3-30 09:19
Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degreefunction..Finally, we construct a fault-tolerant single-sink spanner with bounded maximum degree, and use it to reduce the maximum degree of our basic .-VFTS. As a result, we get a .-VFTS with .(...) edges and maximum degree .(..).作者: 圓桶 時間: 2025-3-30 13:49
Node-Weighted Network Design in Planar and Minor-Closed Families of Graphsth maximum requirement .. Our result is inspired by, and generalizes, the work of Demaine, Hajiaghayi and Klein [5] who gave constant factor approximation algorithms for node-weighted Steiner tree and Steiner forest problems (and more generally covering 0-1 proper functions) in planar and minor-closed families of graphs.作者: 泄露 時間: 2025-3-30 16:35 作者: overshadow 時間: 2025-3-30 21:17
https://doi.org/10.1007/978-3-8349-9576-6 groups in time, polynomial in the order and simply exponential in the degree; (b) the introduction of the “twisted code equivalence problem,” a generalization of the classical code equivalence problem by admitting a group action on the alphabet. Both of these problems are of independent interest.作者: Badger 時間: 2025-3-31 03:59 作者: 獸皮 時間: 2025-3-31 07:40
Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups groups in time, polynomial in the order and simply exponential in the degree; (b) the introduction of the “twisted code equivalence problem,” a generalization of the classical code equivalence problem by admitting a group action on the alphabet. Both of these problems are of independent interest.作者: 直覺好 時間: 2025-3-31 12:30 作者: EVEN 時間: 2025-3-31 13:43 作者: Anthem 時間: 2025-3-31 20:01 作者: pus840 時間: 2025-4-1 00:20 作者: 原告 時間: 2025-4-1 04:00 作者: corpuscle 時間: 2025-4-1 09:28
Automata, Languages, and Programming978-3-642-31594-7Series ISSN 0302-9743 Series E-ISSN 1611-3349 作者: 灌輸 時間: 2025-4-1 10:59
Kostensenkung bei indirekten Materialien, More precisely, for large ., the entangled value of a random 2-player XOR game with . questions to every player is at least 1.21... times the classical value, for 1???.(1) fraction of all 2-player XOR games.作者: 招惹 時間: 2025-4-1 14:25 作者: tinnitus 時間: 2025-4-1 19:14 作者: 誰在削木頭 時間: 2025-4-2 00:11
Kostensenkung bei indirekten Materialien,(..,…,..)?∈?({0,1}.)., .?°?.(..,…,..)?=?.(…,.(..,…,..), …). We show that there is an .(log..) cost simultaneous protocol for . when .?>?1?+?log., . is any symmetric function and . is .. Previously, an efficient protocol was only known for . when . is symmetric and “compressible”. We also get a non-s
