Chandra Chekuri

Vasilis Livanos

Theor. Comput. Sci., 2024

On Sparsest Cut and Conductance in Directed Polymatroidal Networks.

[BibT_eX]

[DOI]

Anand Louis

CoRR, 2024

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs.

[BibT_eX]

[DOI]

CoRR, 2024

Colorful Priority k-Supplier.

[BibT_eX]

[DOI]

Junkai Song

CoRR, 2024

Contention Resolution for the ℓ-fold union of a matroid via the correlation gap.

[BibT_eX]

[DOI]

Junkai Song

Weizhong Zhang

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Adaptive Out-Orientations with Applications.

[BibT_eX]

[DOI]

Aleksander Bjørn Grodt Christiansen

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms.

[BibT_eX]

[DOI]

Weihao Zhu

Proceedings of the Approximation, 2024

1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

Min-Max Partitioning of Hypergraphs and Symmetric Submodular Functions.

[BibT_eX]

[DOI]

Comb., June, 2023

Efficient parallel implementation of the multiplicative weight update method for graph-based linear programs.

[BibT_eX]

[DOI]

CoRR, 2023

On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms.

[BibT_eX]

[DOI]

CoRR, 2023

Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set.

[BibT_eX]

[DOI]

CoRR, 2023

Approximation Algorithms for Network Design in Non-Uniform Fault Models.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing.

[BibT_eX]

[DOI]

Elfarouk Harb

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Independent Sets in Elimination Graphs with a Submodular Objective.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

Bicriteria Approximation Algorithms for Priority Matroid Median.

[BibT_eX]

[DOI]

Tanvi Bajpai

Proceedings of the Approximation, 2023

2022

Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time.

[BibT_eX]

[DOI]

Math. Oper. Res., November, 2022

Algorithms for Intersection Graphs for t-Intervals and t-Pseudodisks.

[BibT_eX]

[DOI]

Tanmay Inamdar

Adv. Math. Commun., 2022

Improved Throughput for All-or-Nothing Multicommodity Flows with Arbitrary Demands.

[BibT_eX]

[DOI]

SIGMETRICS Perform. Evaluation Rev., 2022

Algorithms for covering multiple submodular constraints and applications.

[BibT_eX]

[DOI]

Tanmay Inamdar

Kasturi R. Varadarajan

Zhao Zhang

J. Comb. Optim., 2022

Approximating Flexible Graph Connectivity via Räcke Tree based Rounding.

[BibT_eX]

[DOI]

CoRR, 2022

(1-ε)-approximate fully dynamic densest subgraph: linear space and faster update time.

[BibT_eX]

[DOI]

CoRR, 2022

Augmentation based Approximation Algorithms for Flexible Network Design.

[BibT_eX]

[DOI]

CoRR, 2022

Densest Subgraph: Supermodularity, Iterative Peeling, and Flow.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Faster and Scalable Algorithms for Densest Subgraph and Decomposition.

[BibT_eX]

[DOI]

Elfarouk Harb

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions.

[BibT_eX]

[DOI]

Calvin Beideman

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

2021

Node-weighted Network Design in Planar and Minor-closed Families of Graphs.

[BibT_eX]

[DOI]

Ali Vakilian

ACM Trans. Algorithms, 2021

Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity Problems.

[BibT_eX]

[DOI]

CoRR, 2021

Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Connectivity.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Faster Algorithms for Rooted Connectivity in Directed Graphs.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Revisiting Priority k-Center: Fairness and Outliers.

[BibT_eX]

[DOI]

Tanvi Bajpai

Deeparnab Chakrabarty

Maryam Negahbani

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

On the Hardness of Approximating the k-Way Hypergraph Cut problem.

[BibT_eX]

[DOI]

Shi Li

Theory Comput., 2020

LP Relaxation and Tree Packing for Minimum k-Cut.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

ℓ 1-Sparsity approximation bounds for packing integer programs.

[BibT_eX]

[DOI]

Math. Program., 2020

Fast LP-based Approximations for Geometric Packing and Covering Problems.

[BibT_eX]

[DOI]

Sariel Har-Peled

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Hypergraph $k$-cut for fixed $k$ in deterministic polynomial time.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Algorithms for Intersection Graphs of Multiple Intervals and Pseudo Disks.

[BibT_eX]

[DOI]

Tanmay Inamdar

CoRR, 2019

On Approximating Partial Set Cover and Generalizations.

[BibT_eX]

[DOI]

Zhao Zhang

CoRR, 2019

$\ell_1$-sparsity Approximation Bounds for Packing Integer Programs.

[BibT_eX]

[DOI]

CoRR, 2019

Parallelizing greedy for submodular set function maximization in matroids and beyond.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

On Approximating (Sparse) Covering Integer Programs.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Submodular Function Maximization in Parallel via the Multilinear Relaxation.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

LP Relaxation and Tree Packing for Minimum k-cuts.

[BibT_eX]

[DOI]

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

\ell _1 -sparsity Approximation Bounds for Packing Integer Programs.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2019

2018

Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs.

[BibT_eX]

[DOI]

Marcin Pilipczuk

SIAM J. Discret. Math., 2018

Approximation Algorithms for Euler Genus and Related Problems.

[BibT_eX]

[DOI]

Anastasios Sidiropoulos

SIAM J. Comput., 2018

Minimum Cuts and Sparsification in Hypergraphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Fast Approximations for Metric-TSP via Linear Programming.

[BibT_eX]

[DOI]

CoRR, 2018

A Note on Iterated Rounding for the Survivable Network Design Problem.

[BibT_eX]

[DOI]

Thapanapong Rukkanchanunt

Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

Randomized MWU for Positive LPs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Congestion Minimization for Multipath Routing via Multiroute Flows.

[BibT_eX]

[DOI]

Mark Idleman

Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations.

[BibT_eX]

[DOI]

Shalmoli Gupta

Proceedings of the Approximation, 2018

2017

A note on approximate strengths of edges in a hypergraph.

[BibT_eX]

[DOI]

CoRR, 2017

Computing minimum cuts in hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Approximating Multicut and the Demand Graph.

[BibT_eX]

[DOI]

Vivek Madan

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Graph Coloring.

[BibT_eX]

[DOI]

Michael Langberg

Encyclopedia of Algorithms, 2016

Multicommodity Flow, Well-linked Terminals and Routing Problems.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Polynomial Bounds for the Grid-Minor Theorem.

[BibT_eX]

[DOI]

Julia Chuzhoy

J. ACM, 2016

A note on the Survivable Network Design Problem.

[BibT_eX]

[DOI]

Thapanapong Rukkanchanunt

CoRR, 2016

A Fast Approximation for Maximum Weight Matroid Intersection.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation.

[BibT_eX]

[DOI]

Vivek Madan

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut.

[BibT_eX]

[DOI]

Vivek Madan

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Multicommodity Flows and Cuts in Polymatroidal Networks.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

The all-or-nothing flow problem in directed graphs with symmetric demand pairs.

[BibT_eX]

[DOI]

Math. Program., 2015

Centrality of trees for capacitated k-center.

[BibT_eX]

[DOI]

Math. Program., 2015

Approximability of Capacitated Network Design.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Algorithmica, 2015

Degree-3 Treewidth Sparsifiers.

[BibT_eX]

[DOI]

Julia Chuzhoy

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Delay-constrained unicast and the triangle-cast problem.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2015

On Multiplicative Weight Updates for Concave and Submodular Function Maximization.

[BibT_eX]

[DOI]

T. S. Jayram

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Streaming Algorithms for Submodular Function Maximization.

[BibT_eX]

[DOI]

Shalmoli Gupta

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

On Element-Connectivity Preserving Graph Simplification.

[BibT_eX]

[DOI]

Thapanapong Rukkanchanunt

Proceedings of the Algorithms - ESA 2015, 2015

2014

A Graph Reduction Step Preserving Element-Connectivity and Packing Steiner Trees and Forests.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes.

[BibT_eX]

[DOI]

Rico Zenklusen

SIAM J. Comput., 2014

2013

The All-or-Nothing Multicommodity Flow Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Flow-cut gaps for integer and fractional multiflows.

[BibT_eX]

[DOI]

Christophe Weibel

J. Comb. Theory B, 2013

Large-treewidth graph decompositions and applications.

[BibT_eX]

[DOI]

Julia Chuzhoy

Proceedings of the Symposium on Theory of Computing Conference, 2013

Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Maximum Edge-Disjoint Paths in k-Sums of Graphs.

[BibT_eX]

[DOI]

Guyslain Naves

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor.

[BibT_eX]

[DOI]

Theory Comput., 2012

Improved algorithms for orienteering and related problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

On the set multicover problem in geometric settings.

[BibT_eX]

[DOI]

Kenneth L. Clarkson

Sariel Har-Peled

ACM Trans. Algorithms, 2012

Pruning 2-Connected Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2012

Prize-Collecting Survivable Network Design in Node-Weighted Graphs.

[BibT_eX]

[DOI]

Ali Vakilian

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Set connectivity problems in undirected graphs and the directed steiner network problem.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2011

Maximizing a Monotone Submodular Function Subject to a Matroid Constraint.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Buy-at-Bulk Network Design with Protection.

[BibT_eX]

[DOI]

Spyridon Antonakopoulos

Lisa Zhang

Math. Oper. Res., 2011

Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding.

[BibT_eX]

[DOI]

Rico Zenklusen

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Prize-collecting Steiner Problems on Planar Graphs.

[BibT_eX]

[DOI]

MohammadHossein Bateni

Dániel Marx

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Submodular Cost Allocation Problem and Applications.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Approximation Algorithms for Submodular Multiway Partition.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design.

[BibT_eX]

[DOI]

Mohammad R. Salavatipour

SIAM J. Comput., 2010

Prize-Collecting Steiner Tree and Forest in Planar Graphs

[BibT_eX]

[DOI]

Richard Matthew McCutchen

CoRR, 2010

New Models and Algorithms for Throughput Maximization in Broadcast Scheduling - (Extended Abstract).

[BibT_eX]

[DOI]

Louiqa Raschid

Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures.

[BibT_eX]

[DOI]

Rico Zenklusen

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Edge-Disjoint Paths in Planar Graphs with Constant Congestion.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Disjoint bases in a polymatroid.

[BibT_eX]

[DOI]

Gruia Calinescu

Random Struct. Algorithms, 2009

Randomized Pipage Rounding for Matroid Polytopes and Applications

[BibT_eX]

[DOI]

CoRR, 2009

Longest Wait First for Broadcast Scheduling

[BibT_eX]

[DOI]

CoRR, 2009

Foreword.

[BibT_eX]

[DOI]

Luca Trevisan

Algorithmica, 2009

A Note on Multiflows and Treewidth.

[BibT_eX]

[DOI]

Algorithmica, 2009

Longest Wait First for Broadcast Scheduling [Extended Abstract].

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, 7th International Workshop, 2009

Online scheduling to minimize the maximum delay factor.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Topology Formation for Wireless Mesh Network Planning.

[BibT_eX]

[DOI]

Chun-cheng Chen

Diego Klabjan

Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009

A Graph Reduction Step Preserving Element-Connectivity and Applications.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2009

On the set multi-cover problem in geometric settings.

[BibT_eX]

[DOI]

Kenneth L. Clarkson

Sariel Har-Peled

Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

Truthful Mechanisms via Greedy Iterative Packing.

[BibT_eX]

[DOI]

Iftah Gamzu

Proceedings of the Approximation, 2009

Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Multicommodity Flow, Well-linked Terminals and Routing Problems.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Approximate Integer Decompositions for Undirected Network Design Problems.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2008

Min-Cost 2-Connected Subgraphs With k Terminals

[BibT_eX]

[DOI]

CoRR, 2008

Algorithms for 2-Route Cut Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Single-Sink Network Design with Vertex Connectivity Requirements.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

2007

An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem.

[BibT_eX]

[DOI]

Theory Comput., 2007

Multicommodity demand flow in a tree and packing integer programs.

[BibT_eX]

[DOI]

Marcelo Mydlarz

ACM Trans. Algorithms, 2007

Edge-disjoint paths revisited.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

Routing and network design with robustness to changing or uncertain traffic demands.

[BibT_eX]

[DOI]

SIGACT News, 2007

Hardness of robust network design.

[BibT_eX]

[DOI]

Gianpaolo Oriolo

Maria Grazia Scutellà

Networks, 2007

Non-Cooperative Multicast and Facility Location Games.

[BibT_eX]

[DOI]

IEEE J. Sel. Areas Commun., 2007

Approximation Algorithms for Orienteering with Time Windows

[BibT_eX]

[DOI]

CoRR, 2007

Approximation Algorithms for the Unsplittable Flow Problem.

[BibT_eX]

[DOI]

Algorithmica, 2007

Approximation algorithms for node-weighted buy-at-bulk network design.

[BibT_eX]

[DOI]

Mohammad R. Salavatipour

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2007

2006

An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow.

[BibT_eX]

[DOI]

Theory Comput., 2006

On average throughput and alphabet size in network coding.

[BibT_eX]

[DOI]

Christina Fragouli

Emina Soljanin

IEEE Trans. Inf. Theory, 2006

Embedding k-Outerplanar Graphs into l 1.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2006

The Steiner k-Cut Problem.

[BibT_eX]

[DOI]

Sudipto Guha

Joseph Naor

SIAM J. Discret. Math., 2006

Special Issue: FOCS 2003.

[BibT_eX]

[DOI]

Daniele Micciancio

J. Comput. Syst. Sci., 2006

A greedy approximation algorithm for the group Steiner problem.

[BibT_eX]

[DOI]

Guy Even

Discret. Appl. Math., 2006

Design tools for transparent optical networks.

[BibT_eX]

[DOI]

Bell Labs Tech. J., 2006

On Achievable Information Rates in Single-Source Non-Uniform Demand Networks.

[BibT_eX]

[DOI]

Christina Fragouli

Emina Soljanin

Proceedings of the Proceedings 2006 IEEE International Symposium on Information Theory, 2006

Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design.

[BibT_eX]

[DOI]

Mohammad R. Salavatipour

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2006

2005

A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Routing bandwidth guaranteed paths with local restoration in label switched networks.

[BibT_eX]

[DOI]

IEEE J. Sel. Areas Commun., 2005

On a bidirected relaxation for the MULTIWAY CUT problem.

[BibT_eX]

[DOI]

Anupam Gupta

Amit Kumar

Discret. Appl. Math., 2005

Building Edge-Failure Resilient Networks.

[BibT_eX]

[DOI]

Algorithmica, 2005

Multicommodity flow, well-linked terminals, and routing problems.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

A Recursive Greedy Algorithm for Walks in Directed Graphs.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Sampling Bounds for Stochastic Optimization.

[BibT_eX]

[DOI]

Moses Charikar

Proceedings of the Approximation, 2005

2004

Approximation Algorithms for Minimizing AverageWeighted Completion Time.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Scheduling - Algorithms, Models, and Performance Analysis., 2004

A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2004

On Multidimensional Packing Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Incremental Clustering and Dynamic Information Retrieval.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Multi-processor scheduling to minimize flow time with epsilon resource augmentation.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Edge-Disjoint Paths in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Maximum Coverage Problem with Group Budget Constraints and Applications.

[BibT_eX]

[DOI]

Amit Kumar

Proceedings of the Approximation, 2004

2003

Embedding k-outerplanar graphs into l1.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Multicommodity Demand Flow in a Tree.

[BibT_eX]

[DOI]

Marcelo Mydlarz

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Approximating Steiner k-Cuts.

[BibT_eX]

[DOI]

Sudipto Guha

Joseph Naor

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2001

Approximation Techniques for Average Completion Time Scheduling.

[BibT_eX]

[DOI]

SIAM J. Comput., 2001

An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines.

[BibT_eX]

[DOI]

Michael A. Bender

J. Algorithms, 2001

Approximation Schemes for Preemptive Weighted Flow Time

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Algorithms for minimizing weighted flow time.

[BibT_eX]

[DOI]

An Zhu

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Approximation algorithms for the metric labeling problem via a new linear programming formulation.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

A deterministic algorithm for the cost-distance problem.

[BibT_eX]

[DOI]

Joseph Naor

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

2000

Conjunctive query containment revisited.

[BibT_eX]

[DOI]

Anand Rajaraman

Theor. Comput. Sci., 2000

Performance guarantees for the TSP with a parameterized triangle inequality.

[BibT_eX]

[DOI]

Michael A. Bender

Inf. Process. Lett., 2000

A PTAS for the multiple knapsack problem.

[BibT_eX]

[DOI]

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Blocking probability estimates in a partitioned sector TDMA system.

[BibT_eX]

[DOI]

Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M 2000), 2000

1999

Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication).

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

Approximation Algorithms for Directed Steiner Problems.

[BibT_eX]

[DOI]

J. Algorithms, 1999

Precedence Constrained Scheduling to Minimize Sum of Weighted Completion Times on a Single Machine.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1999

Minimizing Weighted Completion Time on a Single Machine.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

On Multi-Dimensional Packing Problems.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Approximation algorithms for scheduling problems.

[BibT_eX]

[DOI]

PhD thesis, 1998

Filtering with Approximate Predicates.

[BibT_eX]

[DOI]

Narayanan Shivakumar

Hector Garcia-Molina

Proceedings of the VLDB'98, 1998

Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Approximating a Finite Metric by a Small Number of Tree Metrics.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Experimental Study of Minimum Cut Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996

Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication).

[BibT_eX]

[DOI]

Donald Aingworth

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Profile-driven Instruction Level Parallel Scheduling with Application to Super Blocks.

[BibT_eX]

[DOI]

Michael S. Schlansker

Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture, 1996

1995

Scheduling Problems in Parallel Query Optimization.

[BibT_eX]

[DOI]

Waqar Hasan