
Inhaltsverzeichnis
A New Point of NP-Hardness for 2-to-1 Label Cover. -Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems . -Additive Approximation for Near-Perfect Phylogeny Construction. -Improved Spectral-Norm Bounds for Clustering. -Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs . -What s the Frequency, Kenneth? : Sublinear Fourier Sampling Off the Grid. -Improved Hardness Results for Profit Maximization Pricing Problems
with Unlimited Supply. -Online Flow Time Scheduling in the Presence of Preemption Overhead. -Prize-Collecting Survivable Network Design in Node-Weighted Graphs . -Approximating Minimum-Cost Connected
T
-Joins . -iBGP and Constrained Connectivity. -Online Scheduling of Jobs with Fixed Start Times on Related Machines . -A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems . -Approximating Bounded Occurrence Ordering CSPs . -On the NP-Hardness of Max-Not-2 . -The Remote Set Problem on Lattices . -Approximation Algorithms for Generalized and Variable-Sized Bin Covering . -Approximating Minimum Linear Ordering Problems. -New Approximation Results for Resource Replication Problems . -Maximum Matching in Semi-streaming with Few Passes . -Improved Inapproximability for TSP . -Approximation Algorithm for Non-boolean MAX
k
-CSP . -Planarizing an Unknown Surface. -The Projection Games Conjecture and the NP-Hardness of In
n
-Approximating Set-Cover. -New and Improved Bounds for the Minimum Set Cover Problem. -Hardness of Vertex Deletion and Project Scheduling. -Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues . -Circumventing
d
-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four (Extended Abstract). -Spectral Norm of Symmetric Functions . -Almost K-Wise vs. K-Wise Independent Permutations, and Uniformity for General Group Actions. -Testing Permanent Oracles Revisited. -Limitations of Local Filters of Lipschitz and Monotone Functions . -Testing Lipschitz Functions on Hypergrid Domains . -Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic. -Multiple-Choice Balanced Allocation in (Almost) Parallel. -Optimal Hitting Sets for Combinatorial Shapes. -Tight Bounds for Testing
k
-Linearity. -Pseudorandomness for Linear Length Branching Programs and Stack Machines. -A Discrepancy Lower Bound for Information Complexity. -On the Coin Weighing Problem with the Presence of Noise. -Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming. -An Explicit VC-Theorem for Low-Degree Polynomials . -Tight Bounds on the Threshold for Permuted
k
-Colorability. -Sparse and Lopsided Set Disjointness via Information Theory. -Maximal Empty Boxes Amidst Random Points . -Rainbow Connectivity of Sparse Random Graphs. -Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors . -Two-Sided Error Proximity Oblivious Testing (Extended Abstract). -Mirror Descent Based Database Privacy. -Analysis of
k
-Means++ for Separable Data. -A Sharper Local Lemma with Improved Applications. -Finding Small Sparse Cuts by Random Walk. -On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation. -A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller Codes. -A Combination of Testability and Decodability by Tensor Products Extractors for Turing-Machine Sources.
Es wurden noch keine Bewertungen abgegeben. Schreiben Sie die erste Bewertung zu "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques" und helfen Sie damit anderen bei der Kaufentscheidung.