Search results for "integrality gap"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	Jeff Cheeger, Bruce Kleiner, Assaf Naor	A (log n)Omega(1) Integrality Gap for the Sparsest Cut SDP.	FOCS	2009	DBLP DOI BibTeX RDF	Sparsest Cut problem, Heisenberg group, semidefinite programming, metric embeddings, integrality gap
2	Claire Mathieu, Alistair Sinclair	Sherali-adams relaxations of the matching polytope.	STOC	2009	DBLP DOI BibTeX RDF	0-1 programming, matching polytope, maximum matching, linear programming relaxation, integrality gap, lift-and-project
2	Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar	Hardness of routing with congestion in directed graphs.	STOC	2007	DBLP DOI BibTeX RDF	all-or-nothing flow, hardness of approximation, multicommodity flow, edge-disjoint paths, integrality gap, congestion minimization
2	Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani	Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut.	STOC	2007	DBLP DOI BibTeX RDF	Lovasz-Schrijver hierarchy, approximation algorithms, linear programming, integrality gap
2	Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd	Multicommodity demand flow in a tree and packing integer programs.	ACM Transactions on Algorithms	2007	DBLP DOI BibTeX RDF	Integer multicommodity flow, packing integer program, approximation algorithm, tree, integrality gap
2	Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Yuster, Raphael Yuster	Approximation algorithms and hardness results for cycle packing problems.	ACM Transactions on Algorithms	2007	DBLP DOI BibTeX RDF	Cycle packing, edge-disjoint, approximation algorithms, hardness of approximation, integrality gap
2	Chandra Chekuri, Christina Fragouli, Emina Soljanin	On average throughput and alphabet size in network coding.	IEEE Transactions on Information Theory	2006	DBLP DOI BibTeX RDF	linear programming integrality gap, routing, multicast, throughput, network coding
2	Mohammad R. Salavatipour, Jacques Verstraëte	Disjoint Cycles: Integrality Gap, Hardness, and Approximation.	IPCO	2005	DBLP DOI BibTeX RDF
2	Subhash Khot, Nisheeth K. Vishnoi	The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1.	FOCS	2005	DBLP DOI BibTeX RDF
2	Michael E. Saks, Alex Samorodnitsky, Leonid Zosin	A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks.	Combinatorica	2004	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C20, 90C35, 90B10
2	Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd	Multicommodity Demand Flow in a Tree.	ICALP	2003	DBLP DOI BibTeX RDF	integer multicommodity flow, packing integer program, approximation algorithm, tree, integrality gap
2	Kunal Talwar	The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap.	IPCO	2002	DBLP BibTeX RDF
2	Sylvia C. Boyd, Geneviève Labonté	Finding the Exact Integrality Gap for Small Traveling Salesman Problems.	IPCO	2002	DBLP BibTeX RDF
2	Naveen Garg, Rohit Khandekar, Goran Konjevod, R. Ravi, F. Sibel Salman, Amitabh Sinha II	On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-Bulk Network Design Problem.	IPCO	2001	DBLP DOI BibTeX RDF
1	Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen	On the Integrality Gap of the Subtour LP for the 1, 2-TSP.	LATIN	2012	DBLP DOI BibTeX RDF
1	Alexander Grigoriev, Joris van de Klundert	A note on the integrality gap of an ILP formulation for the periodic maintenance problem.	Oper. Res. Lett.	2011	DBLP DOI BibTeX RDF
1	Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen	On the Integrality Gap of the Subtour LP for the 1,2-TSP	CoRR	2011	DBLP BibTeX RDF
1	Deeparnab Chakrabarty, Jochen Könemann, David Pritchard	Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound.	Oper. Res. Lett.	2010	DBLP DOI BibTeX RDF
1	David Pritchard	An LP with Integrality Gap 1+epsilon for Multidimensional Knapsack	CoRR	2010	DBLP BibTeX RDF
1	Deeparnab Chakrabarty, Jochen Könemann, David Pritchard	Integrality Gap of the Hypergraphic Relaxation of Steiner Trees: a short proof of a 1.55 upper bound	CoRR	2010	DBLP BibTeX RDF
1	Subhash Khot, Preyas Popat, Rishi Saket	Approximate Lasserre Integrality Gap for Unique Games.	APPROX-RANDOM	2010	DBLP DOI BibTeX RDF
1	Lirong Xia, Vincent Conitzer, Ariel D. Procaccia	A scheduling approach to coalitional manipulation.	ACM Conference on Electronic Commerce	2010	DBLP DOI BibTeX RDF	coalitional manipulation, positional scoring rules, scheduling, social choice
1	Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità	An improved LP-based approximation for steiner tree.	STOC	2010	DBLP DOI BibTeX RDF	approximation algorithms, randomized algorithms, network design, linear programming relaxations
1	Ken-ichi Kawarabayashi, Bruce A. Reed	Odd cycle packing.	STOC	2010	DBLP DOI BibTeX RDF	odd cycle, packing
1	Jon Lee, Maxim Sviridenko, Jan Vondrák	Matroid matching: the power of local search.	STOC	2010	DBLP DOI BibTeX RDF	Sherali-Adams hierarchy, local search, matching, matroid
1	Alper Atamtürk, Vishnu Narayanan	Conic mixed-integer rounding cuts.	Math. Program.	2010	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 90C11, 90C25, 90C57
1	Jeff Cheeger, Bruce Kleiner, Assaf Naor	A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP	CoRR	2009	DBLP BibTeX RDF
1	Prasad Raghavendra, David Steurer	How to Round Any CSP.	FOCS	2009	DBLP DOI BibTeX RDF	rounding scheme, approximation algorithm, sensitivity analysis, semidefinite programming, constraint satisfaction problems, dimension reduction, integrality gap
1	Prasad Raghavendra, David Steurer	Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES.	FOCS	2009	DBLP DOI BibTeX RDF	SDP hierarchies, Sherali-Adams hierarchy, integrality gap construction, approximation algorithms, semidefinite programming, hardness of approximation, unique games conjecture
1	Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour	A logarithmic approximation for unsplittable flow on line graphs.	SODA	2009	DBLP DOI BibTeX RDF
1	Robert Krauthgamer, Joseph Naor, Roy Schwartz	Partitioning graphs into balanced components.	SODA	2009	DBLP DOI BibTeX RDF
1	Viswanath Nagarajan, Maxim Sviridenko	On the maximum quadratic assignment problem.	SODA	2009	DBLP DOI BibTeX RDF
1	Toniann Pitassi, Nathan Segerlind	Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures.	SODA	2009	DBLP DOI BibTeX RDF
1	Prasad Raghavendra, David Steurer	Towards computing the Grothendieck constant.	SODA	2009	DBLP DOI BibTeX RDF
1	MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami	MaxMin allocation via degree lower-bounded arborescences.	STOC	2009	DBLP DOI BibTeX RDF	approximation algorithms, linear programming, graphs, lift-and-project
1	Madhur Tulsiani	CSP gaps and reductions in the lasserre hierarchy.	STOC	2009	DBLP DOI BibTeX RDF	constraint satisfaction, semidefinite programming, integrality gaps
1	Julia Chuzhoy, Sanjeev Khanna	Polynomial flow-cut gaps and hardness of directed cut problems.	J. ACM	2009	DBLP DOI BibTeX RDF	Directed multicut, hardness of approximation, sparsest cut
1	Chandra Chekuri, Alina Ene, Nitish Korula	Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
1	Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, Maxim Sviridenko	On Hardness of Pricing Items for Single-Minded Bidders.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
1	Piotr Berman, Bhaskar DasGupta, Marek Karpinski	Approximating Transitive Reductions for Directed Networks.	WADS	2009	DBLP DOI BibTeX RDF
1	Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd	A Note on Multiflows and Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Product multicommodity flow, Treewidth, Edge-disjoint paths
1	Stacy L. Janak, Christodoulos A. Floudas	Improving unit-specific event based continuous-time approaches for batch processes: Integrality gap and task splitting.	Computers & Chemical Engineering	2008	DBLP DOI BibTeX RDF
1	Geneviève Benoit, Sylvia Boyd	Finding the Exact Integrality Gap for Small Traveling Salesman Problems.	Math. Oper. Res.	2008	DBLP DOI BibTeX RDF
1	Chandra Chekuri, Guy Even, Anupam Gupta, Danny Segev	Set connectivity problems in undirected graphs and the directed Steiner network problem.	SODA	2008	DBLP DOI BibTeX RDF
1	Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy	Approximation algorithms for labeling hierarchical taxonomies.	SODA	2008	DBLP DOI BibTeX RDF
1	Tanmoy Chakraborty, Julia Chuzhoy, Sanjeev Khanna	Network design for vertex connectivity.	STOC	2008	DBLP DOI BibTeX RDF	approximation algorithms, network design, hardness of approximation, vertex connectivity
1	Prasad Raghavendra	Optimal algorithms and inapproximability results for every CSP?	STOC	2008	DBLP DOI BibTeX RDF	dictatorship tests, rounding schemes, semidefinite programming, constraint satisfaction problem, unique games conjecture
1	Deeparnab Chakrabarty, Gagan Goel	On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP.	FOCS	2008	DBLP DOI BibTeX RDF
1	Arash Asadpour, Uriel Feige, Amin Saberi	Santa Claus Meets Hypergraph Matchings.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
1	Guy Kortsarz, Michael Langberg, Zeev Nutov	Approximating Maximum Subgraphs without Short Cycles.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
1	Monaldo Mastrolilli, Nikolaus Mutsanas, Ola Svensson	Approximating Single Machine Scheduling with Scenarios.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
1	Viswanath Nagarajan, R. Ravi	The Directed Minimum Latency Problem.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
1	Thành Nguyen	A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF	ATSP, LP relaxation
1	Aravind Srinivasan	Budgeted Allocations in the Full-Information Setting.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
1	Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani	New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem.	IPCO	2008	DBLP DOI BibTeX RDF
1	Konstantinos Georgiou, Avner Magen, Iannis Tourlakis	Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities.	IPCO	2008	DBLP DOI BibTeX RDF
1	Viswanath Nagarajan, Maxim Sviridenko	Tight Bounds for Permutation Flow Shop Scheduling.	IPCO	2008	DBLP DOI BibTeX RDF
1	Arrigo Zanette, Matteo Fischetti, Egon Balas	Can Pure Cutting Plane Algorithms Work?.	IPCO	2008	DBLP DOI BibTeX RDF	Gomory Cuts, Degeneracy in Linear Programming, Lexicographic Dual Simplex, Computational Analysis, Cutting Plane Methods
1	Brian C. Dean, Adam Griffis, Adam A. Whitley	Approximation Algorithms for k-Hurdle Problems.	LATIN	2008	DBLP DOI BibTeX RDF
1	Jochen Könemann, Ojas Parekh, David Pritchard	Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees.	WAOA	2008	DBLP DOI BibTeX RDF
1	Egon Balas, Anureet Saxena	Optimizing over the split closure.	Math. Program.	2008	DBLP DOI BibTeX RDF
1	Wenceslas Fernandez de la Vega, Claire Kenyon-Mathieu	Linear programming relaxations of maxcut.	SODA	2007	DBLP DOI BibTeX RDF
1	Yossi Azar, Iftah Gamzu, Shai Gutner	Truthful unsplittable flow for large capacity networks.	SPAA	2007	DBLP DOI BibTeX RDF	combinatorial and multi-unit auctions, approximation algorithms, mechanism design, primal-dual method
1	Julia Chuzhoy, Sanjeev Khanna	Polynomial flow-cut gaps and hardness of directed cut problems.	STOC	2007	DBLP DOI BibTeX RDF	concurrent flow, directed multicut, directed sparsest cut, flow-cut gaps, hardness of approximation, multicommodity flow
1	Chandra Chekuri, Sanjeev Khanna	Edge-disjoint paths revisited.	ACM Transactions on Algorithms	2007	DBLP DOI BibTeX RDF	multicommodity flow relaxation, approximation algorithm, greedy algorithm, Edge-disjoint paths
1	Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani	A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.	IEEE Conference on Computational Complexity	2007	DBLP DOI BibTeX RDF
1	Naveen Garg, Amit Kumar	Minimizing Average Flow-time : Upper and Lower Bounds.	FOCS	2007	DBLP DOI BibTeX RDF
1	Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis	Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy.	FOCS	2007	DBLP DOI BibTeX RDF
1	Hamed Hatami, Avner Magen, Evangelos Markakis	Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to l1 Embeddability of Negative Type Metrics.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
1	Amit Kumar, Yogish Sabharwal	The Priority k-Median Problem.	FSTTCS	2007	DBLP DOI BibTeX RDF
1	Alper Atamtürk, Vishnu Narayanan	Cuts for Conic Mixed-Integer Programming.	IPCO	2007	DBLP DOI BibTeX RDF	Integer programming, branch-and-cut, conic programming
1	Zachary Friggstad, Mohammad R. Salavatipour	Approximability of Packing Disjoint Cycles.	ISAAC	2007	DBLP DOI BibTeX RDF
1	Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann	The Stackelberg Minimum Spanning Tree Game.	WADS	2007	DBLP DOI BibTeX RDF
1	Matteo Fischetti, Andrea Lodi	Optimizing over the first Chvátal closure.	Math. Program.	2007	DBLP DOI BibTeX RDF	Separation problems, Chvátal-Gomory cuts, Integer programs, Computational analysis
1	Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd	An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow.	Theory of Computing	2006	DBLP DOI BibTeX RDF
1	Zoë Abrams, Ho-Lin Chen, Leonidas J. Guibas, Jie Liu, Feng Zhao	Kinetically stable task assignment for networks of microservers.	IPSN	2006	DBLP DOI BibTeX RDF	matchings, stochastic processes
1	Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko	Tight approximation algorithms for maximum general assignment problems.	SODA	2006	DBLP DOI BibTeX RDF
1	Robert Krauthgamer, Yuval Rabani	Improved lower bounds for embeddings into L1.	SODA	2006	DBLP DOI BibTeX RDF
1	Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber	A quasi-PTAS for unsplittable flow on line graphs.	STOC	2006	DBLP DOI BibTeX RDF	scheduling, approximation algorithms, resource allocation, approximation scheme, unsplittable flow
1	Nikhil Bansal, Maxim Sviridenko	The Santa Claus problem.	STOC	2006	DBLP DOI BibTeX RDF	maximin, unrelated machines, scheduling, approximation algorithms, resource allocation
1	Moses Charikar, Konstantin Makarychev, Yury Makarychev	Near-optimal algorithms for unique games.	STOC	2006	DBLP DOI BibTeX RDF	unique games, approximation algorithms, semidefinite programming, constraint satisfaction problems
1	Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd	Edge-disjoint paths in Planar graphs with constant congestion.	STOC	2006	DBLP DOI BibTeX RDF	Planar graphs, multicommodity flow, edge-disjoint paths
1	Nikhil R. Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi	Integrality gaps for sparsest cut and minimum linear arrangement problems.	STOC	2006	DBLP DOI BibTeX RDF
1	Iannis Tourlakis	New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy.	IEEE Conference on Computational Complexity	2006	DBLP DOI BibTeX RDF
1	James R. Lee, Assaf Naor	Lp metrics on the Heisenberg group and the Goemans-Linial conjecture.	FOCS	2006	DBLP DOI BibTeX RDF
1	Michael Langberg, Yuval Rabani, Chaitanya Swamy	Approximation Algorithms for Graph Homomorphism Problems.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	Viswanath Nagarajan, R. Ravi	Minimum Vehicle Routing with a Common Deadline.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	Martin Hoefer	Non-cooperative Facility Location and Covering Games.	ISAAC	2006	DBLP DOI BibTeX RDF
1	Virginie Gabrel	Strengthened 0-1 linear formulation for the daily satellite mission planning.	J. Comb. Optim.	2006	DBLP DOI BibTeX RDF	Stable set polytope, Satellite mission planning, Cocomparability graph, Integer programming
1	Sylvia Boyd, Paul Elliott-Magwood	Computing the integrality gap of the asymmetric travelling salesman problem.	Electronic Notes in Discrete Mathematics	2005	DBLP DOI BibTeX RDF
1	Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson	Approximating the smallest k-edge connected spanning subgraph by LP-rounding.	SODA	2005	DBLP DOI BibTeX RDF
1	Michael Krivelevich, Zeev Nutov, Raphael Yuster	Approximation algorithms for cycle packing problems.	SODA	2005	DBLP DOI BibTeX RDF
1	James R. Lee	On distance scales, embeddings, and efficient relaxations of the cut cone.	SODA	2005	DBLP DOI BibTeX RDF
1	Özgür Sümer	Partial covering of hypergraphs.	SODA	2005	DBLP DOI BibTeX RDF	partial hypergraph cover, partial set cover, greedy algorithm
1	Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev	O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems.	STOC	2005	DBLP DOI BibTeX RDF	directed balanced separator, directed sparsest cut, min 2CNF deletion, min UnCut, min multicut
1	Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor	Quadratic forms on graphs.	STOC	2005	DBLP DOI BibTeX RDF	Grothendieck's inequaity, rounding techniques, correlation clustering, spin glasses
1	Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee	Improved approximation algorithms for minimum-weight vertex separators.	STOC	2005	DBLP DOI BibTeX RDF	vertex separators, approximation algorithms, semidefinite programming, treewidth, metric embeddings
1	Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang	Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.	FOCS	2005	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra	On Non-Approximability for Quadratic Programs.	FOCS	2005	DBLP DOI BibTeX RDF
1	Subhash Khot	On the Unique Games Conjecture.	FOCS	2005	DBLP DOI BibTeX RDF