close
1.

電子ブック
ＥＢ
1. Efficient Approximation and Online Algorithms
Evripidis Bampis, Klaus Jansen, Takeo Kanade, Claire Kenyon
出版情報: Springer eBooks Computer Science , Springer Berlin / Heidelberg, 2006
所蔵情報: loading…
2.

電子ブック
ＥＢ
2. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Irit Dinur, Klaus Jansen, Takeo Kanade, Joseph Naor, Jos? Rolim
出版情報: Springer eBooks Computer Science , Springer Berlin Heidelberg, 2009
所蔵情報: loading…
3.

電子ブック
ＥＢ
3. Approximation and Online Algorithms
Evripidis Bampis, Klaus Jansen, Takeo Kanade
出版情報: Springer eBooks Computer Science , Springer Berlin Heidelberg, 2010
所蔵情報: loading…
4.

電子ブック
ＥＢ
4. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Maria Serna, Klaus Jansen, Takeo Kanade, Jos? Rolim, Ronen Shaltiel
出版情報: Springer eBooks Computer Science , Springer Berlin Heidelberg, 2010
所蔵情報: loading…
目次情報: 続きを見る
Contributed Talks of APPROX
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem / Hyung-Chan An ; Robert D. Kleinberg ; David B. Shmoys
Improved Inapproximability for Submodular Maximization / Per Austrin
Approximation Algorithms for the Directed k-Tour and k-Stroll Problems / MohammadHossein Bateni ; Julia Chuzhoy
Submodular Secretary Problem and Extensions / MohammadTaghi Hajiaghayi ; Morteza Zadimoghaddam
Approximation Algorithms for Min-Max Generalization Problems / Piotr Berman ; Sofya Raskhodnikova
Min-Power Strong Connectivity / Gruia Calinescu
The Complexity of Approximately Counting Stable Matchings / Prasad Chebolu ; Leslie Ann Goldberg ; Russell Martin
Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs / Victor Chepoi ; Feodor F. Dragan ; Ilan Newman ; Yuri Rabinovich ; Yann Vaxès
Approximating Linear Threshold Predicates / Mahdi Cheraghchi ; Johan Håstad ; Marcus Isaksson ; Ola Svensson
Approximating Sparsest Cut in Graphs of Bounded Treewidth / Eden Chlamtac ; Robert Krauthgamer ; Prasad Raghavendra
On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors / Irit Dinur ; Igor Shinkar
Vertex Sparsifiers: New Results from Old Techniques / Matthias Englert ; Anupam Gupta ; Harald Räcke ; Inbal Talgam-Cohen ; Kunal Talwar
PTAS for Weighted Set Cover on Unit Squares / Thomas Erlebach ; Erik Jan van Leeuwen
Improved Lower Bounds for the Universal and a priori TSP / Igor Gorodezky ; Gwen Spencer
Proximity Algorithms for Nearly-Doubling Spaces / Lee-Ad Gottlieb
Matrix Sparsification and the Sparse Null Space Problem / Tyler Neylon
The Checkpoint Problem / Rohit Khandekar ; Guy Kortsarz ; Julián Mestre
The Euclidean Distortion of Flat Tori / Ishay Haviv ; Oded Regev
Online Embeddings / Piotr Indyk ; Avner Magen ; Anastasios Sidiropoulos ; Anastasios Zouzias
Approximation Algorithms for Intersection Graphs / Frank Kammer ; Torsten Tholey ; Heiko Voepel
An O(log n)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs / Ken-ichi Kawarabayashi ; Yusuke Kobayashi
Improved Algorithm for the Half-Disjoint Paths Problem
Approximate Lasserre Integrality Gap for Unique Games / Subhash Khot ; Preyas Popat ; Rishi Saket
Exploiting Concavity in Bimatrix Games: New Polynomially Tractable Subclasses / Spyros Kontogiannis ; Paul Spirakis
Maximum Flows on Disjoint Paths / Guyslain Naves ; Nicolas Sonnerat ; Adrian Vetta
Approximation Algorithms for Reliable Stochastic Combinatorial Optimization / Evdokia Nikolova
How To Schedule When You Have to Buy Your Energy / Kirk Pruhs ; Cliff Stein
Improving Integrality Gaps via Chvátal-Gomory Rounding / Mohit Singh
Contributed Talks of RANDOM
Uniform Derandomization from Pathetic Lower Bounds / Eric Allender ; V. Arvind ; Fengming Wang
Testing Boolean Function Isomorphism / Noga Alon ; Eric Blais
Better Size Estimation for Sparse Matrix Products / Rasmus Resen Amossen ; Andrea Campagna ; Rasmus Pagh
Low Rate Is Insufficient for Local Testability / Eli Ben-Sasson ; Michael Viderman
Reconstruction Threshold for the Hardcore Model / Nayantara Bhatnagar ; Allan Sly ; Prasad Tetali
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners / Arnab Bhattacharyya ; Elena Grigorescu ; Madhav Jha ; Kyomin Jung ; David P. Woodruff
Monotonicity Testing and Shortest-Path Routing on the Cube / Jop Briët ; Sourav Chakraborty ; David García-Soriano ; Arie Matsliah
Better Gap-Hamming Lower Bounds via Better Round Elimination / Joshua Brody ; Amit Chakrabarti ; Thomas Vidick ; Ronald de Wolf
Propagation Connectivity of Random Hypergraphs / Amin Coja-Oghlan ; Mikael Onsjö ; Osamu Watanabe
Improved Pseudorandom Generators for Depth 2 Circuits / Anindya De ; Omid Etesami ; Luca Trevisan ; Madhur Tulsiani
The Structure of Winning Strategies in Parallel Repetition Games / Elazar Goldenberg
Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries / Elya Dolev ; Dana Ron
Periodicity in Streams / Funda Ergun ; Hossein Jowhari ; Mert Saglam
Rumor Spreading on Random Regular Graphs and Expanders / Nikolaos Fountoulakis
On Testing Computability by Small Width OBDDs / Oded Goldreich
Learning and Lower Bounds for AC0 with Threshold Gates / Parikshit Gopalan ; Rocco A. Servedio
Liftings of Tree-Structured Markov Chains (Extended Abstract) / Thomas P. Hayes ; Alistair Sinclair
Constructive Proofs of Concentration Bounds / Russell Impagliazzo ; Valentine Kabanets
Almost-Euclidean Subspaces of l1N via Tensor Products: A Simple Approach to Randomness Reduction / Stanislaw Szarek
Testing Outerplanarity of Bounded Degree Graphs / Yuichi Yoshida ; Hiro Ito
Two-Source Extractors Secure against Quantum Adversaries / Roy Kasher ; Julia Kempe
Locally Testable vs. Locally Decodable Codes / Tali Kaufman
Differential Privacy and the Fat-Shattering Dimension of Linear Queries / Aaron Roth
Two Theorems on List Decoding (Extended Abstract) / Atri Rudra ; Steve Uurtamo
Delaying Satisfiability for Random 2SAT / Dan Vilenchik
Improved Rounding for Parallel Repeated Unique Games / David Steurer
A Query Efficient Non-adaptive Long Code Test with Perfect Completeness / Suguru Tamaki
Relativized Worlds without Worst-Case to Average-Case Reductions for NP / Thomas Watson
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field
Author Index
Contributed Talks of APPROX
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem / Hyung-Chan An ; Robert D. Kleinberg ; David B. Shmoys
Improved Inapproximability for Submodular Maximization / Per Austrin
5.

電子ブック
ＥＢ
5. Approximation and Online Algorithms
Klaus Jansen, Takeo Kanade, Roberto Solis-Oba
出版情報: Springer eBooks Computer Science , Springer Berlin Heidelberg, 2011
所蔵情報: loading…
目次情報: 続きを見る
WAOA 2010
Strategic Multiway Cut and Multicut Games / Elliot Anshelevich ; Bugra Caskurlu ; Ameya Hate
Approximating Directed Buy-at-Bulk Network Design / Spyridon Antonakopoulos
New Lower Bounds for Certain Classes of Bin Packing Algorithms / János Balogh ; József Békési ; Gábor Galambos
On the Approximation Complexity Hierarchy / Magnus Bordewich
The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers / Patrick Briest ; Heiko Röglin
Tradeoff between Energy and Throughput for Online Deadline Scheduling / Ho-Leung Chan ; Tak-Wah Lam ; Rongbin Li
New Models and Algorithms for Throughput Maximization in Broadcast Scheduling (Extended Abstract) / Chandra Chekuri ; Avigdor Gal ; Sungjin Im ; Samir Khuller ; Jian Li ; Richard McCutchen ; Benjamin Moseley ; Louiqa Raschid
Densest k-Subgraph Approximation on Intersection Graphs / Danny Z. Chen ; Rudolf Fleischer
The Train Delivery Problem - Vehicle Routing Meets Bin Packing / Aparna Das ; Claire Mathieu ; Shay Mozes
An FPTAS for Flows over Time with Aggregate Arc Capacities / Daniel Dressler ; Martin Skutella
List Factoring and Relative Worst Order Analysis / Martin R. Ehmsen ; Jens S. Kohrt ; Kim S. Larsen
Approximation Algorithms for Domination Search / Fedor V. Fomin ; Petr A. Golovach ; Dimitrios M. Thilikos
Lower Bounds for Smith's Rule in Stochastic Machine Scheduling / Caroline Jagtenberg ; Uwe Schwiegelshohn ; Marc Uetz
Approximating Survivable Networks with Minimum Number of Steiner Points / Lior Kamma ; Zeev Nutov
A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks / Andreas Karrenbauer ; Thomas Rothvo?
Online Tracking of the Dominance Relationship of Distributed Multi-dimensional Data / Chi-Man Liu ; Hing-Fung Ting
How to Play Unique Games on Expanders / Konstantin Makarychev ; Yury Makarychev
Online Ranking for Tournament Graphs / Adrian Vladu
Throughput Maximization for Periodic Packet Routing on Trees and Grids / Britta Peis ; Andreas Wiese
k-Edge-Connectivity: Approximation and LP Relaxation / David Pritchard
Minimizing Maximum Flowtime of Jobs with Arbitrary Parallelizability / Kirk Pruhs ; Julien Robert ; Nicolas Schabanel
An Improved Algorithm for Online Rectangle Filling / Rob van Stee
Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems / Tomoyuki Yamakami
Author Index
WAOA 2010
Strategic Multiway Cut and Multicut Games / Elliot Anshelevich ; Bugra Caskurlu ; Ameya Hate
Approximating Directed Buy-at-Bulk Network Design / Spyridon Antonakopoulos
6.

電子ブック
ＥＢ
6. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Leslie Ann Goldberg, Klaus Jansen, Takeo Kanade, R. Ravi, Jos? D. P. Rolim
出版情報: Springer eBooks Computer Science , Springer Berlin Heidelberg, 2011
所蔵情報: loading…
7.

電子ブック
ＥＢ
7. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
International Workshop on Approximation Algorithms for Combinatorial Optimizational Problems, Chandra Chekuri, Takeo Kanade, Klaus Jansen, Jos?? D.P. Rolim, Luca Trevisan
出版情報: Springer eBooks Computer Science , Springer Berlin / Heidelberg, 2005
所蔵情報: loading…
目次情報: 続きを見る
Contributed Talks of APPROX
The Network as a Storage Device: Dynamic Routing with Bounded Buffers / Stanislav Angelov ; Sanjeev Khanna ; Keshav Kunal
Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT / Adi Avidor ; Uri Zwick
What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs / Kamalika Chaudhuri ; Satish Rao ; Samantha Riesenfeld ; Kunal Talwar
A Rounding Algorithm for Approximating Minimum Manhattan Networks / Victor Chepoi ; Karim Nouioua ; Yann Vaxès
Packing Element-Disjoint Steiner Trees / Joseph Cheriyan ; Mohammad R. Salavatipour
Approximating the Bandwidth of Caterpillars / Uriel Feige
Where's the Winner? Max-Finding and Sorting with Metric Costs / Anupam Gupta ; Amit Kumar
What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization / Martin Pál ; Ramamoorthi Ravi ; Amitabh Sinha
The Complexity of Making Unique Choices: Approximating 1-in-k SAT / Venkatesan Guruswami ; Luca Trevisan
Approximating the Distortion / Alexander Hall ; Christos Papadimitriou
Beating a Random Assignment / Boulos Harb ; Sampath Kannan ; Andrew McGregor ; Gustav Hast
Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints / V.S. Anil Kumar ; Madhav V. Marathe ; Srinivasan Parthasarathy ; Aravind Srinivasan
Approximation Algorithms for Network Design and Facility Location with Service Capacities / Jens Maßberg ; Jens Vygen
Finding Graph Matchings in Data Streams
A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses / Julián Mestre
Efficient Approximation of Convex Recolorings / Shlomo Moran ; Sagi Snir
Approximation Algorithms for Requirement Cut on Graphs / Viswanath Nagarajan
Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems / Jan Remy ; Angelika Steger
Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy / Iannis Tourlakis
Contributed Talks of RANDOM
Bounds for Error Reduction with Few Quantum Queries / Sourav Chakraborty ; Jaikumar Radhakrishnan ; Nandakumar Raghunathan
Sampling Bounds for Stochastic Optimization / Moses Charikar ; Chandra Chekuri
An Improved Analysis of Mergers / Zeev Dvir ; Amir Shpilka
Finding a Maximum Independent Set in a Sparse Random Graph / Eran Ofek
On the Error Parameter of Dispersers / Ronen Gradwohl ; Guy Kindler ; Omer Reingold ; Amnon Ta-Shma
Tolerant Locally Testable Codes / Atri Rudra
A Lower Bound on List Size for List Decoding / Salil Vadhan
A Lower Bound for Distribution-Free Monotonicity Testing / Shirley Halevy ; Eyal Kushilevitz
On Learning Random DNF Formulas Under the Uniform Distribution / Jeffrey C. Jackson ; Rocco A. Servedio
Derandomized Constructions of k-Wise (Almost) Independent Permutations / Eyal Kaplan ; Moni Naor
Testing Periodicity / Oded Lachish ; Ilan Newman
The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem / Vadim Lyubashevsky
The Online Clique Avoidance Game on Random Graphs / Martin Marciniszyn ; Reto Spöhel
A Generating Function Method for the Average-Case Analysis of DPLL / Rémi Monasson
A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas / Cristopher Moore ; Gabriel Istrate ; Demetrios Demopoulos ; Moshe Y. Vardi
Mixing Points on a Circle / Dana Randall ; Peter Winkler
Derandomized Squaring of Graphs / Eyal Rozenman
Tight Bounds for String Reconstruction Using Substring Queries / Dekel Tsur
Reconstructive Dispersers and Hitting Set Generators / Christopher Umans
The Tensor Product of Two Codes Is Not Necessarily Robustly Testable / Paul Valiant
Fractional Decompositions of Dense Hypergraphs / Raphael Yuster
Author Index
Contributed Talks of APPROX
The Network as a Storage Device: Dynamic Routing with Bounded Buffers / Stanislav Angelov ; Sanjeev Khanna ; Keshav Kunal
Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT / Adi Avidor ; Uri Zwick
8.

電子ブック
ＥＢ
8. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Moses Charikar, Klaus Jansen, Takeo Kanade, Omer Reingold, Jos? D. P. Rolim
出版情報: Springer eBooks Computer Science , Springer Berlin Heidelberg, 2007
所蔵情報: loading…
9.

電子ブック
ＥＢ
9. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Ashish Goel, Klaus Jansen, Takeo Kanade, Jos? D. P. Rolim, Ronitt Rubinfeld
出版情報: Springer eBooks Computer Science , Springer Berlin Heidelberg, 2008
所蔵情報: loading…
10.

電子ブック
ＥＢ
10. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Josep D?az, Josep Daiaz, Klaus Jansen, Takeo Kanade, Jos? D. P. Rolim, Uri Zwick
出版情報: Springer eBooks Computer Science , Springer Berlin Heidelberg, 2006
所蔵情報: loading…
目次情報: 続きを見る
Invited Talks
On Nontrivial Approximation of CSPs / Johan Hastad
Analysis of Algorithms on the Cores of Random Graphs / Nick Wormald
Contributed Talks of APPROX
Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs / Christoph Ambuhl ; Thomas Erlebach ; Matus Mihal'ak ; Marc Nunkesser
Approximating Precedence-Constrained Single Machine Scheduling by Coloring / Monaldo Mastrolilli ; Ola Svensson
Minimizing Setup and Beam-On Times in Radiation Therapy / Nikhil Bansal ; Don Coppersmith ; Baruch Schieber
On the Value of Preemption in Scheduling / Yair Bartal ; Stefano Leonardi ; Gil Shallom ; Rene Sitters
An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs / Benjamin E. Birnbaum ; Kenneth J. Goldman
Tight Results on Minimum Entropy Set Cover / Jean Cardinal ; Samuel Fiorini ; Gwenael Joret
A Tight Lower Bound for the Steiner Point Removal Problem on Trees. T.-H. / Hubert Chan ; Donglin Xia ; Goran Konjevod ; Andrea Richa
Single-Source Stochastic Routing / Shuchi Chawla ; Tim Roughgarden
An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem / Chandra Chekuri ; Martin Pal
Online Algorithms to Minimize Resource Reallocations and Network Communication / Sashka Davis ; Jeff Edmonds ; Russell Impagliazzo
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs / Leah Epstein ; Magnus M. Halldorsson ; Asaf Levin ; Hadas Shachnai
Combinatorial Algorithms for Data Migration to Minimize Average Completion Time / Rajiv Gandhi ; Julian Mestre
LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times / Alexander Grigoriev ; Maxim Sviridenko ; Marc Uetz
Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees / Mohammad Taghi Hajiaghayi ; Guy Kortsarz ; Mohammad R. Salavatipour
Improved Algorithms for Data Migration / Samir Khuller ; Yoo-Ah Kim ; Azarakhsh Malekian
Approximation Algorithms for Graph Homomorphism Problems / Michael Langberg ; Yuval Rabani ; Chaitanya Swamy
Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem / Retsef Levi
Hardness of Preemptive Finite Capacity Dial-a-Ride Inge Li Gortz
Minimum Vehicle Routing with a Common Deadline / Viswanath Nagarajan ; R. Ravi
Stochastic Combinatorial Optimization with Controllable Risk Aversion Level / Anthony Man-Cho So ; Jiawei Zhang ; Yinyu Ye
Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems Zeev Nutov
Better Approximations for the Minimum Common Integer Partition Problem David P. Woodruff
Contributed Talks of Random
On Pseudorandom Generators with Linear Stretch in NC[superscript 0] / Benny Applebaum ; Yuval Ishai ; Eyal Kushilevitz
A Fast Random Sampling Algorithm for Sparsifying Matrices / Sanjeev Arora ; Elad Hazan ; Satyen Kale
The Effect of Boundary Conditions on Mixing Rates of Markov Chains / Nayantara Bhatnagar ; Sam Greenberg ; Dana Randall
Adaptive Sampling and Fast Low-Rank Matrix Approximation / Amit Deshpande ; Santosh Vempala
Robust Local Testability of Tensor Products of LDPC Codes / Irit Dinur ; Madhu Sudan ; Avi Wigderson
Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods / Petros Drineas ; Michael W. Mahoney ; S. Muthukrishnan
Dobrushin Conditions and Systematic Scan / Martin Dyer ; Leslie Ann Goldberg ; Mark Jerrum
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems / Uriel Feige ; Elchanan Mossel ; Dan Vilenchik
Robust Mixing Murali K. Ganapathy
Approximating Average Parameters of Graphs / Oded Goldreich ; Dana Ron
Local Decoding and Testing for Homomorphisms / Elena Grigorescu ; Swastik Kopparty
Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy Dan Gutfreund
Randomness-Efficient Sampling Within NC[superscript 1] Alexander Healy
Monotone Circuits for the Majority Function / Shlomo Hoory ; Avner Magen ; Toniann Pitassi
Space Complexity vs. Query Complexity / Oded Lachish ; Ilan Newman ; Asaf Shapira
Consistency of Local Density Matrices Is QMA-Complete Yi-Kai Liu
On Bounded Distance Decoding for General Lattices / Yi-Kai Liu ; Vadim Lyubashevsky ; Daniele Micciancio
Threshold Functions for Asymmetric Ramsey Properties Involving Cliques / Martin Marciniszyn ; Jozef Skokan ; Reto Spohel ; Angelika Steger
Distance Approximation in Bounded-Degree and General Sparse Graphs / Sharon Marko
Fractional Matching Via Balls-and-Bins / Rajeev Motwani ; Rina Panigrahy ; Ying Xu
A Randomized Solver for Linear Systems with Exponential Convergence / Thomas Strohmer ; Roman Vershynin
Maintaining External Memory Efficient Hash Tables / Philipp Woelfel
Author Index
Invited Talks
On Nontrivial Approximation of CSPs / Johan Hastad
Analysis of Algorithms on the Cores of Random Graphs / Nick Wormald
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼