Approximation, randomization, and combinatorial optimization : algorithms and techniques : 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013, proceedings
Approximation, randomization, and combinatorial optimization : algorithms and techniques : 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013, proceedings
复制标题
近似、随机化和组合优化：算法和技术：第 16 届国际研讨会，APPROX 2013 和第 17 届国际研讨会，RANDOM 2013，美国加利福尼亚州伯克利，2013 年 8 月 21-23 日，会议记录
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
P. Raghavendra
中科院分区：
文献类型：
--
作者：
P. Raghavendra
动态图流中的谱稀疏化在线随机广义指派问题关于近似排序约束满足问题的NP-困难性用拾取和丢弃采样近似大频率矩。推广Indyk和Woodruff的分层方法：流上基于频率的矢量的递归草图。无向图上的容量限制网络设计安排子集测试：一次性，连续，以及它们之间的关系。关于凸容器中相似凸体的总周长。-部分区间集覆盖-可扩展性和最优性之间的权衡。在线方形到方形包装。在线非透视调度，同时最小化所有凸函数。缩小最大值，降低成本：新的在线包装和覆盖问题。不对称网络中的多个旅行推销员近似指数化和具有凹报酬和延迟反馈的Bandit问题二进制Paintshop问题的近似性。运动修复的近似算法。改进的近似色数的困难性Hamilton图亏格的伪逼近最大匹配的局部计算近似方案在图表上绘制地球移动器距离在线多维负载平衡。一个新的正则性引理和低门限秩图的快速逼近算法平面图上的截断问题条件随机场，种植约束满足和熵集中。从有损失或有噪声的数据中找到重要的数据。私人学习和消毒：纯粹与近似差分隐私。Z2上硬核模型的相共存和缓慢混合一种快速的稀疏网络私有数据发布算法用于连通性和直径的局部重构器和容差测试器。超网格上单调性检验的最优下界Nonabel群的小偏差集：Alon-Roichman定理的去随机化。你可以做什么与协调的样品。鲁棒随机性放大器：上限和下限。随机可满足性的选择能力随机高维几何图的连通性匹配向量族和大模上的最不发达国家通过多项式恒等式测试的同时共轭的显式Noether归一化在计数器自动机语言中测试成员资格。测试线性同构的紧下界。随机高效曲线采样器。平均半径列表解码的组合限制。零知识LTC及其应用小误差高频矩估计的一个紧下界改进的FPTAS多自旋系统。通过傅立叶分析正则分支程序的伪随机性提升代码的绝对可靠测试。关于k-CNF公式的平均灵敏度和密度二维硬核模型相变边界的改进。
Spectral Sparsification in Dynamic Graph Streams.- The Online Stochastic Generalized Assignment Problem.- On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems.- Approximating Large Frequency Moments with Pick-and-Drop Sampling.- Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams.- Capacitated Network Design on Undirected Graphs.- Scheduling Subset Tests: One-Time, Continuous, and How They Relate.- On the Total Perimeter of Homothetic Convex Bodies in a Convex Container.- Partial Interval Set Cover - Trade-Offs between Scalability and Optimality.- Online Square-into-Square Packing.- Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions.- Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems.- Multiple Traveling Salesmen in Asymmetric Metrics.- Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback.- The Approximability of the Binary Paintshop Problem.- Approximation Algorithms for Movement Repairmen.- Improved Hardness of Approximating Chromatic Number.- A Pseudo-approximation for the Genus of Hamiltonian Graphs.- A Local Computation Approximation Scheme to Maximum Matching.- Sketching Earth-Mover Distance on Graph Metrics.- Online Multidimensional Load Balancing.- A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs.- Interdiction Problems on Planar Graphs.- Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration.- Finding Heavy Hitters from Lossy or Noisy Data.- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy.- Phase Coexistence and Slow Mixing for the Hard-Core Model on Z2.- Fast Private Data Release Algorithms for Sparse Queries.- Local Reconstructors and Tolerant Testers for Connectivity and Diameter.- An Optimal Lower Bound for Monotonicity Testing over Hypergrids.- Small-Bias Sets for Nonabelian Groups: Derandomizations of the Alon-Roichman Theorem.- What You Can Do with Coordinated Samples.- Robust Randomness Amplifiers: Upper and Lower Bounds.- The Power of Choice for Random Satisfiability.- Connectivity of Random High Dimensional Geometric Graphs.- Matching-Vector Families and LDCs over Large Modulo.- Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing.- Testing Membership in Counter Automaton Languages.- Tight Lower Bounds for Testing Linear Isomorphism.- Randomness-Efficient Curve Samplers.- Combinatorial Limitations of Average-Radius List Decoding.- Zero Knowledge LTCs and Their Applications.- A Tight Lower Bound for High Frequency Moment Estimation with Small Error.- Improved FPTAS for Multi-spin Systems.- Pseudorandomness for Regular Branching Programs via Fourier Analysis.- Absolutely Sound Testing of Lifted Codes.- On the Average Sensitivity and Density of k-CNF Formulas.- Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions.