Baruch Schieber

J. Sched., February, 2024

Approximations and Hardness of Packing Partially Ordered Items.

[BibT_eX]

[DOI]

CoRR, 2024

2023

Interweaving Real-Time Jobs with Energy Harvesting to Maximize Throughput.

[BibT_eX]

[DOI]

Bhargav Samineni

Soroush Vahidi

Proceedings of the WALCOM: Algorithms and Computation, 2023

Quick Minimization of Tardy Processing Time on a Single Machine.

[BibT_eX]

[DOI]

Pranav Sitaraman

Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

Parallel Longest Common SubSequence Analysis In Chapel.

[BibT_eX]

[DOI]

Proceedings of the IEEE High Performance Extreme Computing Conference, 2023

Approximating Connected Maximum Cuts via Local Search.

[BibT_eX]

[DOI]

Soroush Vahidi

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

2022

Satisfying Complex Top-k Fairness Constraints by Preference Substitutions.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2022

Partially Disjoint k Shortest Paths.

[BibT_eX]

[DOI]

CoRR, 2022

Rank Aggregation with Proportionate Fairness.

[BibT_eX]

[DOI]

Proceedings of the SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

2020

Fully Dynamic MIS in Uniformly Sparse Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

The Euclidean k-Supplier Problem.

[BibT_eX]

[DOI]

Viswanath Nagarajan

Math. Oper. Res., 2020

Maximizing Throughput in Flow Shop Real-Time Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

2019

Constrained submodular maximization via greedy local search.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2019

Flexible Resource Allocation to Interval Jobs.

[BibT_eX]

[DOI]

Dmitriy Katz

Algorithmica, 2019

Fully Dynamic Maximal Independent Set with Sublinear in n Update Time.

[BibT_eX]

[DOI]

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

Scalable Fair Clustering.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

Generalized Assignment via Submodular Optimization with Reserved Capacity.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Complexity and inapproximability results for the Power Edge Set problem.

[BibT_eX]

[DOI]

J. Comb. Optim., 2018

A Theory and Algorithms for Combinatorial Reoptimization.

[BibT_eX]

[DOI]

Algorithmica, 2018

Fully dynamic maximal independent set with sublinear update time.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Brief Announcement: Approximation Algorithms for Preemptive Resource Allocation.

[BibT_eX]

[DOI]

Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018

Generalized Assignment of Time-Sensitive Item Groups.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2016

All-Or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Flexible Resource Allocation for Clouds and All-Optical Networks.

[BibT_eX]

[DOI]

Dmitriy Katz

CoRR, 2016

Brief Announcement: Flexible Resource Allocation for Clouds and All-Optical Networks.

[BibT_eX]

[DOI]

Dmitriy Katz

Venkatesan T. Chakaravarthy

Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

Subgraph Counting: Color Coding Beyond Trees.

[BibT_eX]

[DOI]

Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium, 2016

Real-Time k-bounded Preemptive Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, 2016

2015

Real-time scheduling to minimize machine busy times.

[BibT_eX]

[DOI]

J. Sched., 2015

The Container Selection Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2013

The Euclidean k-Supplier Problem.

[BibT_eX]

[DOI]

Viswanath Nagarajan

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

The Approximability of the Binary Paintshop Problem.

[BibT_eX]

[DOI]

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

2011

Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy.

[BibT_eX]

[DOI]

Algorithmica, 2011

2010

Dynamic pricing for impatient bidders.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

Minimizing Busy Time in Multiple Machine Real-time Scheduling.

[BibT_eX]

[DOI]

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

2009

Throughput maximization of real-time scheduling with batching.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

2008

Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2008

Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2008

2007

Preface.

[BibT_eX]

[DOI]

IBM J. Res. Dev., 2007

Inventory allocation and transportation scheduling for logistics of network-centric military operations.

[BibT_eX]

[DOI]

IBM J. Res. Dev., 2007

Non-Preemptive Min-Sum Scheduling with Resource Augmentation.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Vehicle Routing and Staffing for Sedan Service.

[BibT_eX]

[DOI]

Transp. Sci., 2006

Minimizing migrations in fair multiprocessor scheduling of persistent tasks.

[BibT_eX]

[DOI]

Tracy Kimbrel

Maxim Sviridenko

J. Sched., 2006

A quasi-PTAS for unsplittable flow on line graphs.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Minimizing Setup and Beam-On Times in Radiation Therapy.

[BibT_eX]

[DOI]

Nikhil Bansal

Don Coppersmith

Proceedings of the Approximation, 2006

2005

Computing the minimum DNF representation of Boolean functions defined by intervals.

[BibT_eX]

[DOI]

Daniel Geist

Ayal Zaks

Discret. Appl. Math., 2005

2004

Resource optimization in QoS multicast routing of real-time multimedia.

[BibT_eX]

[DOI]

Moses Charikar

Joseph Naor

IEEE/ACM Trans. Netw., 2004

Buffer Overflow Management in QoS Switches.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Further Improvements in Competitive Guarantees for QoS Buffering.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

Pushing Dependent Data in Clients-Providers-Servers Systems.

[BibT_eX]

[DOI]

Joseph Naor

Wirel. Networks, 2003

A Note on Scheduling Tall/Small Multiprocessor Tasks with Unit Processing Time to Minimize Maximum Tardiness.

[BibT_eX]

[DOI]

Philippe Baptiste

J. Sched., 2003

Sparse LCS Common Substring Alignment.

[BibT_eX]

[DOI]

Gad M. Landau

Michal Ziv-Ukelson

Inf. Process. Lett., 2003

2002

Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas.

[BibT_eX]

[DOI]

Guy Even

Sudipto Guha

SIAM J. Comput., 2002

Minimizing Service and Operation Costs of Periodic Scheduling.

[BibT_eX]

[DOI]

Math. Oper. Res., 2002

2001

Approximating the Throughput of Multiple Machines in Real-Time Scheduling.

[BibT_eX]

[DOI]

SIAM J. Comput., 2001

A unified approach to approximating resource allocation and scheduling.

[BibT_eX]

[DOI]

J. ACM, 2001

The edge versus path incidence matrix of series-parallel graphs and greedy packing.

[BibT_eX]

[DOI]

Alan J. Hoffman

Discret. Appl. Math., 2001

Online server allocation in a server farm via benefit task systems.

[BibT_eX]

[DOI]

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

2000

Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2000

Message Multicasting in Heterogeneous Networks.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Divide-and-conquer approximation algorithms via spreading metrics.

[BibT_eX]

[DOI]

J. ACM, 2000

Optimal multiple message broadcasting in telephone-like communication systems.

[BibT_eX]

[DOI]

Shlomo Kipnis

Discret. Appl. Math., 2000

Improved approximations of crossings in graph drawings.

[BibT_eX]

[DOI]

Guy Even

Sudipto Guha

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999

Fast Approximate Graph Partitioning Algorithms.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

Bandwidth Allocation with Preemption.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

The Angular-Metric Traveling Salesman Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

Lower Bounds on the Depth of Monotone Arithmetic Computations.

[BibT_eX]

[DOI]

Don Coppersmith

J. Complex., 1999

Efficient Recovery from Power Outage (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Approximating the Throughput of Multiple Machines Under Real-Time Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Guaranteeing Fair Service to Persistent Dependent Tasks.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Computing a Minimum Weightk-Link Path in Graphs with the Concave Monge Property.

[BibT_eX]

[DOI]

J. Algorithms, 1998

Approximating Minimum Feedback Sets and Multicuts in Directed Graphs.

[BibT_eX]

[DOI]

Algorithmica, 1998

Multicasting in Heterogeneous Networks.

[BibT_eX]

[DOI]

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

Minimizing Service and Operation Costs of Periodic Scheduling (Extended Abstract).

[BibT_eX]

[DOI]

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

Competitive Dynamic Bandwidth Allocation.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, 1998

1997

Deterministic Many-to-Many Hot Potato Routing.

[BibT_eX]

[DOI]

Allan Borodin

Yuval Rabani

IEEE Trans. Parallel Distributed Syst., 1997

Navigating in Unfamiliar Geometric Terrain.

[BibT_eX]

[DOI]

Avrim Blum

Prabhakar Raghavan

SIAM J. Comput., 1997

How much can hardware help routing?

[BibT_eX]

[DOI]

J. ACM, 1997

A Tight Bound for Approximating the Square Root.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1997

A Linear-time Algorithm for Computing the Intersection of All Odd Cycles in a Graph.

[BibT_eX]

[DOI]

Leizhen Cai

Discret. Appl. Math., 1997

Spreading Metric Based Graph Partitioning Algorithms.

[BibT_eX]

Proceedings of the Eighth SIAM Conference on Parallel Processing for Scientific Computing, 1997

Improved Approximations for Shallow-Light Spanning Trees.

[BibT_eX]

[DOI]

Joseph Naor

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996

Efficient Routing in Optical Networks.

[BibT_eX]

[DOI]

J. ACM, 1996

A fast parallel algorithm for finding the convex hull of a sorted point set.

[BibT_eX]

[DOI]

Omer Berkman

Int. J. Comput. Geom. Appl., 1996

1995

Computing Global Combine Operations in the Multiport Postal Model.

[BibT_eX]

[DOI]

IEEE Trans. Parallel Distributed Syst., 1995

Competitive Paging with Locality of Reference.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1995

Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality.

[BibT_eX]

[DOI]

J. Algorithms, 1995

optimal Computation of Census Functions in the Postal Model.

[BibT_eX]

[DOI]

Shlomo Kipnis

Discret. Appl. Math., 1995

Computing a Minimum-Weight k-Link Path in Graphs with the Concave Monge Property.

[BibT_eX]

[DOI]

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

Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 1995

Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Calling Names on Nameless Networks

[BibT_eX]

[DOI]

Marc Snir

Inf. Comput., August, 1994

Finding a Minimum-Weight k-Link Path Graphs with the Concae Monge Property and Applications.

[BibT_eX]

[DOI]

Alok Aggarwal

Takeshi Tokuyama

Discret. Comput. Geom., 1994

A Deterministic O(k³)-Competitive k-Server Algorithm for the Circle.

[BibT_eX]

[DOI]

Algorithmica, 1994

Efficient Routing and Scheduling Algorithms for Optical Networks.

[BibT_eX]

[DOI]

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

An Optimal Algorithm for computing Census Functions in Message-Passing Systems.

[BibT_eX]

[DOI]

Shlomo Kipnis

Parallel Process. Lett., 1993

Optimal Doubly Logarithmic Parallel Algorithms Based on Finding All Nearest Smaller Values.

[BibT_eX]

[DOI]

Omer Berkman

J. Algorithms, 1993

Improved selection in totally monotone arrays.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 1993

Computing Global Combine Operations in the Multi-Port Postal Model.

[BibT_eX]

[DOI]

Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing, 1993

Fast Deflection Routing for Packets and Worms (Extended Summary).

[BibT_eX]

[DOI]

Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, 1993

Finding a Minimum Weight K-Link Path in Graphs with Monge Property and Applications.

[BibT_eX]

[DOI]

Alok Aggarwal

Takeshi Tokuyama

Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

1992

Fast Geometric Approximation Techniques and Geometric Embedding Problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1992

The Intractability of Bounded Protocols for On-Line Sequence Transmission over Non-FIFO Channels.

[BibT_eX]

[DOI]

J. ACM, 1992

On Independent Spanning Trees.

[BibT_eX]

[DOI]

Samir Khuller

Inf. Process. Lett., 1992

An Efficient Algorithm for the All Pairs Suffix-Prefix Problem.

[BibT_eX]

[DOI]

Dan Gusfield

Gad M. Landau

Inf. Process. Lett., 1992

Fast Exponentiation Using the Truncation Operation.

[BibT_eX]

[DOI]

Comput. Complex., 1992

Lower Bounds on the Depth of Monotone Arithmetic Computations (Extended Summary)

[BibT_eX]

[DOI]

Don Coppersmith

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Efficient Minimum Cost Matching Using Quadrangle Inequality

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

Lower Bounds for Computations with the Floor Operation.

[BibT_eX]

[DOI]

SIAM J. Comput., 1991

Efficient Parallel Algorithms for Testing k-Connectivity and Finding Disjoint s-t Paths in Graphs.

[BibT_eX]

[DOI]

Samir Khuller

SIAM J. Comput., 1991

On-line Dynamic Programming with Applications to the Prediction of RNA Secondary Structure.

[BibT_eX]

[DOI]

Lawrence L. Larmore

J. Algorithms, 1991

A Lower Bound for Integer Greatest Common Divisor Computations.

[BibT_eX]

[DOI]

J. ACM, 1991

Computing external farthest neighbors for a simple polygon.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1991

Competitive Paging with Locality of Reference (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Navigating in Unfamiliar Geometric Terrain (Preliminary Version)

[BibT_eX]

[DOI]

Avrim Blum

Prabhakar Raghavan

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

The Canadian Traveller Problem.

[BibT_eX]

[DOI]

Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Improved Selection on Totally Monotone Arrays.

[BibT_eX]

[DOI]

James K. Park

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991

Competitive Paging with Locality of Reference (Brief Summary).

[BibT_eX]

[DOI]

Proceedings of the On-Line Algorithms, 1991

Navigating in Unfamiliar Geometric Terrain (Extended Summary).

[BibT_eX]

[DOI]

Avrim Blum

Prabhakar Raghavan

Proceedings of the On-Line Algorithms, 1991

1990

The Power of Multimedia: Combining Point-to-Point and Multiaccess Networks

[BibT_eX]

[DOI]

Inf. Comput., January, 1990

Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1990

1989

Parallel Algorithms for Maximum Bipartite Matchings and Maximum 0-1 Flows.

[BibT_eX]

[DOI]

Shlomo Moran

J. Parallel Distributed Comput., 1989

Finding the Edge Connectivity of Directed Graphs.

[BibT_eX]

[DOI]

J. Algorithms, 1989

Highly Parallelizable Problems (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Calling Names in Nameless Networks.

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, 1989

The Intractability of Bounded Protocols for Non-FIFO Channels.

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, 1989

The Complexity of Approximating the Square Root (Extended Summary)

[BibT_eX]

[DOI]

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s-t Paths in Graphs (Extended Summary)

[BibT_eX]

[DOI]

Samir Khuller

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988

On Finding Lowest Common Ancestors: Simplification and Parallelization.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

On finding most uniform spanning trees.

[BibT_eX]

[DOI]

Zvi Galil

Discret. Appl. Math., 1988

Parallel Construction of a Suffix Tree with Applications.

[BibT_eX]

[DOI]

Algorithmica, 1988

The Power of Multimedia: Combining Point-to Point and Multi-Access Networks.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, 1988

Lower Bounds for Integer Greatest Common Divisor Computations (Extended Summary)

[BibT_eX]

[DOI]

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

Design and analysis of some parallel algorithms

[BibT_eX]

[DOI]

PhD thesis, 1987

Parallel Construction of a Suffix Tree (Extended Abstract).

[BibT_eX]

[DOI]

Gad M. Landau

Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

1986

Parallel Ear Decomposition Search (EDS) and st-Numbering in Graphs.

[BibT_eX]

[DOI]

Yael Maon

Theor. Comput. Sci., 1986

Slowing Sequential Algorithms for Obtaining Fast Distributed and Parallel Algorithms: Maximum Matchings.

[BibT_eX]

[DOI]

Shlomo Moran

Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, 1986

Parallel Ear Decomposition Search (EDS) and St-Numbering in Graphs (Extended Abstract).

[BibT_eX]

[DOI]

Yael Maon