Search results for "integrality"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
114	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
105	Madhur Tulsiani	CSP gaps and reductions in the lasserre hierarchy.	STOC	2009	DBLP DOI BibTeX RDF	constraint satisfaction, semidefinite programming, integrality gaps
103	Toniann Pitassi, Nathan Segerlind	Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures.	SODA	2009	DBLP DOI BibTeX RDF
89	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
81	Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, Roy Schwartz 0002	Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling.	STOC	2008	DBLP DOI BibTeX RDF	linear and semidefinite programming, metric labelling, multiway cut, integrality gaps, unique games conjecture
79	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
67	Mohammad R. Salavatipour, Jacques Verstraëte	Disjoint Cycles: Integrality Gap, Hardness, and Approximation.	IPCO	2005	DBLP DOI BibTeX RDF
67	Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang 0001	Integrality ratio for group Steiner trees and directed steiner trees.	SODA	2003	DBLP BibTeX RDF
67	Sylvia C. Boyd, Geneviève Labonté	Finding the Exact Integrality Gap for Small Traveling Salesman Problems.	IPCO	2002	DBLP DOI BibTeX RDF
60	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
57	Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Verstraëte, Raphael Yuster	Approximation algorithms and hardness results for cycle packing problems.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	Cycle packing, edge-disjoint, approximation algorithms, hardness of approximation, integrality gap
57	Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd	Multicommodity demand flow in a tree and packing integer programs.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	Integer multicommodity flow, packing integer program, approximation algorithm, tree, integrality gap
57	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
55	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
55	Uriel Feige, Gideon Schechtman	On the integrality ratio of semidefinite relaxations of MAX CUT.	STOC	2001	DBLP DOI BibTeX RDF
48	Brian C. Dean, Adam Griffis, Adam A. Whitley	Approximation Algorithms for k-Hurdle Problems.	LATIN	2008	DBLP DOI BibTeX RDF
48	Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani	A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.	CCC	2007	DBLP DOI BibTeX RDF
48	Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani	On earthmover distance, metric labeling, and 0-extension.	STOC	2006	DBLP DOI BibTeX RDF
46	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
43	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
43	Michael E. Saks, Alex Samorodnitsky, Leonid Zosin	A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks.	Comb.	2004	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C20, 90C35, 90B10
43	Sanjeev Arora, Béla Bollobás, László Lovász 0001	Proving Integrality Gaps without Knowing the Linear Program.	FOCS	2002	DBLP DOI BibTeX RDF
41	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
41	Subhash Khot, Rishi Saket	SDP Integrality Gaps with Local ell_1-Embeddability.	FOCS	2009	DBLP DOI BibTeX RDF	integrality, metric, embedding, SDP
41	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
41	Guoli Ding, Li Feng 0001, Wenan Zang	The complexity of recognizing linear systems with certain integrality properties.	Math. Program.	2008	DBLP DOI BibTeX RDF	Total dual integrality, NP-hardness, Linear system, Polyhedron
41	Michael A. Grasso, David S. Ebert, Timothy W. Finin	The Integrality of Speech in Multimodal Interfaces.	ACM Trans. Comput. Hum. Interact.	1998	DBLP DOI BibTeX RDF	direct manipulution, perceptual structure, integrality, natural-language processing, speech recognition, multimodal, input devices, separability, medical informatics, pathology
41	Robert J. K. Jacob, Linda E. Sibert, Daniel C. McFarlane, M. Preston Mullen Jr.	Integrality and Separability of Input Devices.	ACM Trans. Comput. Hum. Interact.	1994	DBLP DOI BibTeX RDF	Polhemus tracker, perceptual space, integrality, interaction techniques, input devices, separability, gesture input
38	Matthias Brugger, Andreas S. Schulz	On the complexity of recognizing integrality and total dual integrality of the {0, 1/2}-closure.	Oper. Res. Lett.	2022	DBLP DOI BibTeX RDF
38	Matthias Brugger, Andreas S. Schulz	On the Complexity of Recognizing Integrality and Total Dual Integrality of the {0, 1/2}-Closure.	CoRR	2021	DBLP BibTeX RDF
38	Patrick Chervet, Roland Grappe, Louis-Hadrien Robert	Box-total dual integrality, box-integrality, and equimodular matrices.	Math. Program.	2021	DBLP DOI BibTeX RDF
36	Konstantinos Georgiou, Avner Magen, Iannis Tourlakis	Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities.	IPCO	2008	DBLP DOI BibTeX RDF
36	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
36	Guy Kortsarz, Michael Langberg, Zeev Nutov	Approximating Maximum Subgraphs without Short Cycles.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
36	Zachary Friggstad, Mohammad R. Salavatipour	Approximability of Packing Disjoint Cycles.	ISAAC	2007	DBLP DOI BibTeX RDF
36	Ronald L. Graham, Jeffrey C. Lagarias, Colin L. Mallows, Allan R. Wilks, Catherine H. Yan	Apollonian Circle Packings: Geometry and Group Theory I. The Apollonian Group.	Discret. Comput. Geom.	2005	DBLP DOI BibTeX RDF
36	Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang	Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.	FOCS	2005	DBLP DOI BibTeX RDF
36	Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra	On Non-Approximability for Quadratic Programs.	FOCS	2005	DBLP DOI BibTeX RDF
36	Robert D. Carr, Santosh S. Vempala	On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems.	Math. Program.	2004	DBLP DOI BibTeX RDF
36	Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd	Edge-Disjoint Paths in Planar Graphs.	FOCS	2004	DBLP DOI BibTeX RDF
36	Alantha Newman, Santosh S. Vempala	Fences Are Futile: On Relaxations for the Linear Ordering Problem.	IPCO	2001	DBLP DOI BibTeX RDF
36	Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin	Approximation algorithms for the metric labeling problem via a new linear programming formulation.	SODA	2001	DBLP BibTeX RDF
34	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
34	Chandra Chekuri, Christina Fragouli, Emina Soljanin	On average throughput and alphabet size in network coding.	IEEE Trans. Inf. Theory	2006	DBLP DOI BibTeX RDF	linear programming integrality gap, routing, multicast, throughput, network coding
34	Mao-cheng Cai, Xiaotie Deng, Wenan Zang	A Min-Max Theorem on Feedback Vertex Sets.	IPCO	1999	DBLP DOI BibTeX RDF	bipartite tournament, totally dual integrality, min-max relation, AMS subject classification. 68Q25, approximation algorithm, 68R10, feedback vertex set
31	Philippe Baptiste, Jacques Carlier, Alexander V. Kononov, Maurice Queyranne, Sergey Sevastyanov, Maxim Sviridenko	Integrality Property in Preemptive Parallel Machine Scheduling.	CSR	2009	DBLP DOI BibTeX RDF
31	Moses Charikar, Konstantin Makarychev, Yury Makarychev	Integrality gaps for Sherali-Adams relaxations.	STOC	2009	DBLP DOI BibTeX RDF	Sherali-Adams hierarchy, lift-and-project methods, local-global metric spaces
31	Iannis Tourlakis	Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
31	Moses Charikar, Michel X. Goemans, Howard J. Karloff	On the Integrality Ratio for Asymmetric TSP.	FOCS	2004	DBLP DOI BibTeX RDF
31	Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi	Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.	FOCS	2003	DBLP DOI BibTeX RDF
31	Kunal Talwar	The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap.	IPCO	2002	DBLP DOI BibTeX RDF
31	Naveen Garg 0001, Rohit Khandekar, Goran Konjevod, R. Ravi 0001, 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
31	Dorit S. Hochbaum	Instant Recognition of Half Integrality and 2-Approximations.	APPROX	1998	DBLP DOI BibTeX RDF
24	Jaroslaw Byrka, Fabrizio Grandoni 0001, 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
24	Ken-ichi Kawarabayashi, Bruce A. Reed	Odd cycle packing.	STOC	2010	DBLP DOI BibTeX RDF	odd cycle, packing
24	Paul Beame, Trinh Huynh, Toniann Pitassi	Hardness amplification in proof complexity.	STOC	2010	DBLP DOI BibTeX RDF	communication complexity, proof complexity
24	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
24	Kenjiro Takazawa	A weighted even factor algorithm.	Math. Program.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 90C27, 05C70
24	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
24	Arash Asadpour, Uriel Feige, Amin Saberi	Santa Claus Meets Hypergraph Matchings.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
24	Thành Nguyen 0001	A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF	ATSP, LP relaxation
24	Ronald L. Graham, Jeffrey C. Lagarias, Colin L. Mallows, Allan R. Wilks, Catherine H. Yan	Apollonian Circle Packings: Geometry and Group Theory III. Higher Dimensions.	Discret. Comput. Geom.	2006	DBLP DOI BibTeX RDF
24	Qingqi Pei, Kefeng Fan, Jinxiu Dai, Jianfeng Ma 0001	An Intelligent Digital Content Protection Framework Between Home Network Receiver Devices.	CIS	2006	DBLP DOI BibTeX RDF
24	Iannis Tourlakis	New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy.	CCC	2006	DBLP DOI BibTeX RDF
24	Egon Balas	Projection, Lifting and Extended Formulation in Integer and Combinatorial Optimization.	Ann. Oper. Res.	2005	DBLP DOI BibTeX RDF	sequential convexification, 0-1 programming, disjunctive programming, lift-and-project
24	Ron Lavi, Chaitanya Swamy	Truthful and Near-Optimal Mechanism Design via Linear Programming.	FOCS	2005	DBLP DOI BibTeX RDF
24	Egon Balas	Projection and Lifting in Combinatorial Optimization.	Computational Combinatorial Optimization	2001	DBLP DOI BibTeX RDF
24	Kenji Kashiwabara, Masataka Nakamura, Takashi Takabatake	Integral Polyhedra Associated with Certain Submodular Functions Defined on 012-Vectors.	IPCO	1999	DBLP DOI BibTeX RDF
22	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
22	Kang Shi, Sriram Subramanian, Pourang Irani	PressureMove: Pressure Input with Mouse Movement.	INTERACT (2)	2009	DBLP DOI BibTeX RDF	integrality of input dimensions, pressure and movement alternative interaction techniques, Pressure-input
22	Ji Hong, Jiang Xubo	An Ignored Factor of User Experience: FEEDBACK-QUALITY.	HCI (1)	2007	DBLP DOI BibTeX RDF	feedback quality, feedback periods, feedback periods integrality, feedback time
22	Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis	Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy.	STOC	2005	DBLP DOI BibTeX RDF	Lovász-Schrijver matrix cuts, inapproximability, integrality gaps
22	Eran Halperin, Robert Krauthgamer	Polylogarithmic inapproximability.	STOC	2003	DBLP DOI BibTeX RDF	integrality ratio, polylogarithmic approximation, approximation algorithms, Steiner tree, hardness of approximation
22	Robert D. Carr, Santosh S. Vempala	Randomized metarounding (extended abstract).	STOC	2000	DBLP DOI BibTeX RDF	polyhedra, randomized rounding, integrality gap
22	Robert J. K. Jacob, Linda E. Sibert	The Perceptual Structure of Multidimensional Input Device Selection.	CHI	1992	DBLP DOI BibTeX RDF	Polhemus tracker, perceptual space, integrality, interaction techniques, input devices, separability, gesture input
19	Frank de Meijer, Renata Sotirov	On Integrality in Semidefinite Programming for Discrete Optimization.	SIAM J. Optim.	2024	DBLP DOI BibTeX RDF
19	Annika Schiemann, Paul Manns	Discretization of Total Variation in Optimization with Integrality Constraint.	CoRR	2024	DBLP DOI BibTeX RDF
19	Eleonora Vercesi, Stefano Gualandi, Monaldo Mastrolilli, Luca Maria Gambardella	On the generation of metric TSP instances with a large integrality gap by branch-and-cut.	Math. Program. Comput.	2023	DBLP DOI BibTeX RDF
19	Suprovat Ghoshal, Euiwoong Lee	On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs.	CoRR	2023	DBLP DOI BibTeX RDF
19	Sander Borst, Daniel Dadush, Sophie Huiberts, Samarth Tiwari	On the integrality gap of binary integer programs with Gaussian data.	Math. Program.	2023	DBLP DOI BibTeX RDF
19	Michele Barbato, Roland Grappe, Mathieu Lacroix, Emiliano Lancini	Box-total dual integrality and edge-connectivity.	Math. Program.	2023	DBLP DOI BibTeX RDF
19	Robert D. Carr, Arash Haddadan, Cynthia A. Phillips	Fractional Decomposition Tree Algorithm: A tool for studying the integrality gap of Integer Programs.	Discret. Optim.	2023	DBLP DOI BibTeX RDF
19	Heidi Benham, Alexander Galarraga, Benjamin Hutz, Joey Lupo, Wayne Peng, Adam Towsley	Integrality and Thurston rigidity for bicritical PCF polynomials.	Period. Math. Hung.	2023	DBLP DOI BibTeX RDF
19	Vera Traub, Jens Vygen	Beating the Integrality Ratio for $s$-$t$-Tours in Graphs.	SIAM J. Comput.	2023	DBLP DOI BibTeX RDF
19	Penny Haxell, Tibor Szabó	Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole.	SODA	2023	DBLP DOI BibTeX RDF
19	Sander Borst, Daniel Dadush, Dan Mikulincer	Integrality Gaps for Random Integer Programs via Discrepancy.	SODA	2023	DBLP DOI BibTeX RDF
19	Mong-Jen Kao	On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem.	SODA	2023	DBLP DOI BibTeX RDF
19	Suprovat Ghoshal, Euiwoong Lee	On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs.	FOCS	2023	DBLP DOI BibTeX RDF
19	Francesco Pisanu	Sur la box-total dual integralité et la totale équimodularité. (On box-total dual integrality and total equimodularity).		2023	RDF
19	Siu-Wing Cheng, Yuchen Mao	Restricted Max-Min Allocation: Integrality Gap and Approximation Algorithm.	Algorithmica	2022	DBLP DOI BibTeX RDF
19	John Martinovic	A note on the integrality gap of cutting and skiving stock instances.	4OR	2022	DBLP DOI BibTeX RDF
19	Vijay V. Vazirani	Cores of Games via Total Dual Integrality, with Applications to Perfect Graphs and Polymatroids.	CoRR	2022	DBLP DOI BibTeX RDF
19	Penny Haxell, Tibor Szabó	Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole.	CoRR	2022	DBLP BibTeX RDF
19	Samuel C. Gutekunst, David P. Williamson	Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.	Math. Oper. Res.	2022	DBLP DOI BibTeX RDF
19	Yingjie Fei, Yudong Chen 0001	Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model.	Math. Oper. Res.	2022	DBLP DOI BibTeX RDF
19	Joseph Paat, Miriam Schlöter, Robert Weismantel	The integrality number of an integer program.	Math. Program.	2022	DBLP DOI BibTeX RDF
19	Refael Hassin, Renata Poznanski	Integrality in the multinetwork min-cost equal-flow problem.	Networks	2022	DBLP DOI BibTeX RDF
19	Shi Li 0001, Bundit Laekhanukit	Polynomial Integrality Gap of Flow LP for Directed Steiner Tree.	SODA	2022	DBLP DOI BibTeX RDF
19	Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan	A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP.	FOCS	2022	DBLP DOI BibTeX RDF
19	Takuro Fukunaga	Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling.	APPROX/RANDOM	2022	DBLP DOI BibTeX RDF