Joseph Naor

According to our database1, Joseph Naor authored at least 231 papers between 1983 and 2017.

Collaborative distances :
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
Non-preemptive buffer management for latency sensitive packets.
J. Scheduling, 2017

A greedy approximation algorithm for minimum-gap scheduling.
J. Scheduling, 2017

Robust Submodular Maximization: Offline and Online Algorithms.
CoRR, 2017

O(depth)-Competitive Algorithm for Online Multi-level Aggregation.
CoRR, 2017

O(depth)-Competitive Algorithm for Online Multi-level Aggregation.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
Equilibria in Online Games.
SIAM J. Comput., 2016

Unified Algorithms for Online Learning and Competitive Analysis.
Math. Oper. Res., 2016

Timing Matters: Online Dynamics in Broadcast Games.
CoRR, 2016

Online Semidefinite Programming.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Online Algorithms for Covering and Packing Problems with Convex Objectives.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015
Near-Optimal Scheduling Mechanisms for Deadline-Sensitive Jobs in Large Computing Clusters.
TOPC, 2015

Hedonic Clustering Games.
TOPC, 2015

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization.
SIAM J. Comput., 2015

A Polylogarithmic-Competitive Algorithm for the k-Server Problem.
J. ACM, 2015

Truthful Online Scheduling with Commitments.
CoRR, 2015

Near-Optimum Online Ad Allocation for Targeted Advertising.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Truthful Online Scheduling with Commitments.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Near optimal placement of virtual network functions.
Proceedings of the 2015 IEEE Conference on Computer Communications, 2015

2014
Smart Grid Network Optimization: Data-Quality-Aware Volume Reduction.
IEEE Systems Journal, 2014

Min-Max Graph Partitioning and Small Set Expansion.
SIAM J. Comput., 2014

Frequency capping in online advertising.
J. Scheduling, 2014

A Truthful Mechanism for Value-Based Scheduling in Cloud Computing.
Theory Comput. Syst., 2014

Near-Optimum Online Ad Allocation for Targeted Advertising.
CoRR, 2014

Online Packing and Covering Framework with Convex Objectives.
CoRR, 2014

A Randomized O(log2 k)-Competitive Algorithm for Metric Bipartite Matching.
Algorithmica, 2014

Brief announcement: deadline-aware scheduling of big-data processing jobs.
Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 2014

Non-Uniform Graph Partitioning.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Submodular Maximization with Cardinality Constraints.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Competitive Analysis via Regularization.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

On the effect of forwarding table size on SDN network utilization.
Proceedings of the 2014 IEEE Conference on Computer Communications, 2014

Competitive Algorithms for Restricted Caching and Matroid Caching.
Proceedings of the Algorithms - ESA 2014, 2014

2013
Fair online load balancing.
J. Scheduling, 2013

Simplex partitioning via exponential clocks and the multiway cut problem.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Efficient online scheduling for deadline-sensitive jobs: extended abstract.
Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

Almost optimal virtual machine placement for traffic intense data centers.
Proceedings of the IEEE INFOCOM 2013, Turin, Italy, April 14-19, 2013, 2013

A Greedy Approximation Algorithm for Minimum-Gap Scheduling.
Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

2012
Dynamic Power Allocation Under Arbitrary Varying Channels - An Online Approach.
IEEE/ACM Trans. Netw., 2012

Randomized Competitive Algorithms for Generalized Caching.
SIAM J. Comput., 2012

The load-distance balancing problem.
Networks, 2012

Unified Algorithms for Online Learning and Competitive Analysis.
Proceedings of the COLT 2012, 2012

A Primal-Dual Randomized Algorithm for Weighted Paging.
J. ACM, 2012

Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints
CoRR, 2012

Near-optimal scheduling mechanisms for deadline-sensitive jobs in large computing clusters.
Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, 2012

Hedonic clustering games.
Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, 2012

Topology-Aware VM Migration in Bandwidth Oversubscribed Datacenter Networks.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Min-Max Graph Partitioning and Small Set Expansion
CoRR, 2011

A Polylogarithmic-Competitive Algorithm for the k-Server Problem
CoRR, 2011

Frequency Capping in Online Advertising.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Data-quality-aware volume reduction in smart grid networks.
Proceedings of the IEEE Second International Conference on Smart Grid Communications, 2011

A Truthful Mechanism for Value-Based Scheduling in Cloud Computing.
Proceedings of the Algorithmic Game Theory, 4th International Symposium, 2011

Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm - (Extended Abstract).
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Online Node-Weighted Steiner Tree and Related Problems.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

A Unified Continuous Greedy Algorithm for Submodular Maximization.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Min-max Graph Partitioning and Small Set Expansion.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

A Polylogarithmic-Competitive Algorithm for the k-Server Problem.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Improved Approximations for k-Exchange Systems - (Extended Abstract).
Proceedings of the Algorithms - ESA 2011, 2011

Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract).
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
The directed circular arrangement problem.
ACM Trans. Algorithms, 2010

Non-Cooperative Cost Sharing Games via Subsidies.
Theory Comput. Syst., 2010

Online time-constrained scheduling in linear and ring networks.
J. Discrete Algorithms, 2010

Towards the Randomized k-Server Conjecture: A Primal-Dual Approach.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Non-Preemptive Buffer Management for Latency Sensitive Packets.
Proceedings of the INFOCOM 2010. 29th IEEE International Conference on Computer Communications, 2010

Dynamic Power Allocation Under Arbitrary Varying Channels - The Multi-User Case.
Proceedings of the INFOCOM 2010. 29th IEEE International Conference on Computer Communications, 2010

Approximation Algorithms for Diversified Search Ranking.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Metrical Task Systems and the k-Server Problem on HSTs.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009
Throughput maximization of real-time scheduling with batching.
ACM Trans. Algorithms, 2009

Survivable Network Design with Degree or Order Constraints.
SIAM J. Comput., 2009

The Online Set Cover Problem.
SIAM J. Comput., 2009

Online Primal-Dual Algorithms for Covering and Packing.
Math. Oper. Res., 2009

The Design of Competitive Online Algorithms via a Primal-Dual Approach.
Foundations and Trends in Theoretical Computer Science, 2009

Partitioning graphs into balanced components.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Toward Optimal Utilization of Shared Random Access Channels.
Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009

Dynamic Power Allocation Under Arbitrary Varying Channels - An Online Approach.
Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009

2008
On the approximability of some network design problems.
ACM Trans. Algorithms, 2008

Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees.
Theory Comput. Syst., 2008

Editorial.
Discrete Applied Mathematics, 2008

The Third Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms.
Discrete Applied Mathematics, 2008

Homogeneous Interference Game in Wireless Networks.
Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Randomized competitive algorithms for generalized caching.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Online multicast with egalitarian cost sharing.
Proceedings of the SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2008

Non-cooperative Cost Sharing Games Via Subsidies.
Proceedings of the Algorithmic Game Theory, First International Symposium, 2008

2007
Algorithmic aspects of bandwidth trading.
ACM Trans. Algorithms, 2007

The Hardness of Metric Labeling.
SIAM J. Comput., 2007

Non-Cooperative Multicast and Facility Location Games.
IEEE Journal on Selected Areas in Communications, 2007

Cut problems in graphs with a budget constraint.
J. Discrete Algorithms, 2007

Real-Time Scheduling with a Budget.
Algorithmica, 2007

Survivable network design with degree or order constraints.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Equilibria in online games.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Maximum-lifetime routing: system optimization & game-theoretic perspectives.
Proceedings of the 8th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, 2007

Algorithmic Aspects of Access Networks Design in B3G/4G Cellular Networks.
Proceedings of the INFOCOM 2007. 26th IEEE International Conference on Computer Communications, 2007

A Primal-Dual Randomized Algorithm for Weighted Paging.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue.
Proceedings of the Algorithms, 2007

An O (log2 k )-Competitive Algorithm for Metric Bipartite Matching.
Proceedings of the Algorithms, 2007

2006
Efficient location area planning for personal communication systems.
IEEE/ACM Trans. Netw., 2006

A general approach to online network optimization problems.
ACM Trans. Algorithms, 2006

The Steiner k-Cut Problem.
SIAM J. Discrete Math., 2006

Covering Problems with Hard Capacities.
SIAM J. Comput., 2006

Scheduling Split Intervals.
SIAM J. Comput., 2006

Efficient algorithms for shared backup allocation in networks with partial information.
J. Comb. Optim., 2006

New hardness results for congestion minimization and machine scheduling.
J. ACM, 2006

Coping with Interference: From Maximum Coverage to Planning Cellular Networks.
Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

Fair online load balancing.
Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

Non-cooperative multicast and facility location games.
Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

Cut Problems in Graphs with a Budget Constraint.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
Asymmetric k-center is log* n-hard to approximate.
J. ACM, 2005

Building Edge-Failure Resilient Networks.
Algorithmica, 2005

Balanced metric labeling.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Traffic engineering of management flows by link augmentations on confluent trees.
Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

On the approximability of some network design problems.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Approximating the average response time in broadcast scheduling.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Online time-constrained scheduling in linear networks.
Proceedings of the INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005

From Balanced Graph Partitioning to Balanced Metric Labeling.
Proceedings of the Algorithms, 2005

Online Primal-Dual Algorithms for Covering and Packing Problems.
Proceedings of the Algorithms, 2005

Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information.
Proceedings of the Algorithms, 2005

2004
Resource optimization in QoS multicast routing of real-time multimedia.
IEEE/ACM Trans. Netw., 2004

A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem.
SIAM J. Discrete Math., 2004

Approximating the Advertisement Placement Problem.
J. Scheduling, 2004

Admission Control in Networks with Advance Reservations.
Algorithmica, 2004

New hardness results for congestion minimization and machine scheduling.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Asymmetric k-center is log* n-hard to approximate.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

The directed circular arrangement problem.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

A general approach to online network optimization problems.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

The Hardness of Metric Labeling.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Machine Minimization for Scheduling Jobs with Interval Constraints.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
Pushing Dependent Data in Clients-Providers-Servers Systems.
Wireless Networks, 2003

Asymmetric k-center is log*n-hard to Approximate
Electronic Colloquium on Computational Complexity (ECCC), 2003

Competitive On-Line Switching Policies.
Algorithmica, 2003

The online set cover problem.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Efficient location area planning for personal communication systems.
Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking, 2003

Real-Time Scheduling with a Budget.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Approximating Steiner k-Cuts.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Algorithmic Aspects of Bandwidth Trading.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2002
Efficient handoff rerouting algorithms: a competitive on-line algorithmic approach.
IEEE/ACM Trans. Netw., 2002

Minimizing Service and Operation Costs of Periodic Scheduling.
Math. Oper. Res., 2002

Scheduling split intervals.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Throughput maximization of real-time scheduling with batching.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Competitive on-line switching policies.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Approximating the Advertisement Placement Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2002

Building Edge-Failure Resilient Networks.
Proceedings of the Integer Programming and Combinatorial Optimization, 2002

On-line Admission Control and Packet Scheduling with Interleaving.
Proceedings of the Proceedings IEEE INFOCOM 2002, 2002

Control Message Aggregation in Group Communication Protocols.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Covering Problems with Hard Capacities.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Routing and Admission Control in Networks with Advance Reservations.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001
A 2-Approximation Algorithm for the Directed Multiway Cut Problem.
SIAM J. Comput., 2001

Approximating the Throughput of Multiple Machines in Real-Time Scheduling.
SIAM J. Comput., 2001

On-Line Load Balancing in a Hierarchical Server Topology.
SIAM J. Comput., 2001

Computing an Optimal Orientation of a Balanced Decomposition Tree for Linear Arrangement Problems.
J. Graph Algorithms Appl., 2001

A unified approach to approximating resource allocation and scheduling.
J. ACM, 2001

Tree packing and approximating k-cuts.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Approximation algorithms for the metric labeling problem via a new linear programming formulation.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

A deterministic algorithm for the cost-distance problem.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000
Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications.
SIAM J. Discrete Math., 2000

An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem.
SIAM J. Comput., 2000

Message Multicasting in Heterogeneous Networks.
SIAM J. Comput., 2000

The Loading Time Scheduling Problem.
J. Algorithms, 2000

Divide-and-conquer approximation algorithms via spreading metrics.
J. ACM, 2000

Dynamic storage allocation with known durations.
Discrete Applied Mathematics, 2000

A unified approach to approximating resource allocation and scheduling.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Directed network design with orientation constraints.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Pushing dependent data in clients-providers-servers systems.
Proceedings of the MOBICOM 2000, 2000

Resource Optimization in QoS Multicast Routing of Real-Time Multimedia.
Proceedings of the Proceedings IEEE INFOCOM 2000, 2000

Efficient Handoff Rerouting Algorithms: A Competitive On-Line Algorithmic Approach.
Proceedings of the Proceedings IEEE INFOCOM 2000, 2000

Dynamic session management for static and mobile users: a competitive on-line algorithmic approach.
Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M 2000), 2000

1999
Fast Approximate Graph Partitioning Algorithms.
SIAM J. Comput., 1999

The Budgeted Maximum Coverage Problem.
Inf. Process. Lett., 1999

Efficient Recovery from Power Outage (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Approximating the Throughput of Multiple Machines Under Real-Time Scheduling.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

On-Line Load Banancing in a Hierarchical Server Topology.
Proceedings of the Algorithms, 1999

1998
Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference.
SIAM J. Comput., 1998

Scheduled Hot-Potato Routing.
J. Graph Algorithms Appl., 1998

Approximating Probability Distributions Using Small Sample Spaces.
Combinatorica, 1998

Approximating Minimum Feedback Sets and Multicuts in Directed Graphs.
Algorithmica, 1998

Multicasting in Heterogeneous Networks.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Minimizing Service and Operation Costs of Periodic Scheduling (Extended Abstract).
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

1997
Fast Approximate Graph Partitioning Algorithms.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Spreading Metric Based Graph Partitioning Algorithms.
Proceedings of the Eighth SIAM Conference on Parallel Processing for Scientific Computing, 1997

A 2-Approximation Algorithm for the Directed Multiway Cut Problem.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Improved Approximations for Shallow-Light Spanning Trees.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Dynamic Storage Allocation with Known Durations.
Proceedings of the Algorithms, 1997

1996
Routing Strategies for Fast Networks.
IEEE Trans. Computers, 1996

Tight Bounds for Dynamic Storage Allocation.
SIAM J. Discrete Math., 1996

Approximation Algorithms for Network Design Problems on Bounded Subsets.
J. Algorithms, 1996

Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications.
Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
Flow in Planar Graphs with Multiple Sources and Sinks.
SIAM J. Comput., 1995

Constructions of Permutation Arrays for Certain Scheduling Cost Measures.
Random Struct. Algorithms, 1995

The Competitiveness of On-Line Assignments.
J. Algorithms, 1995

Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs.
Proceedings of the Integer Programming and Combinatorial Optimization, 1995

Scheduled Hot-Potato Routing.
Proceedings of the Proceedings IEEE INFOCOM '95, 1995

Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract).
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

The Loading Time Scheduling Problem (Extended Abstract).
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
Simple and Fast Algorithms for Linear and Integer Programs With Two Variables per Inequality.
SIAM J. Comput., 1994

The Probabilistic Method Yields Deterministic Parallel Algorithms.
J. Comput. Syst. Sci., 1994

Flow in Planar Graphs with Vertex Capacities.
Algorithmica, 1994

Tight Bounds for Dynamic Storage Allocation.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Approximation Algorithms for the Vertex Feedback Set Problem with Applications to Constraint Satisfaction and Bayesian Inference.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993
The Lattice Structure of Flow in Planar Graphs.
SIAM J. Discrete Math., 1993

Small-Bias Probability Spaces: Efficient Constructions and Applications.
SIAM J. Comput., 1993

Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality.
Math. Program., 1993

1992
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs.
IEEE Trans. Information Theory, 1992

A Linear Time Approach to the Set Maxima Problem.
SIAM J. Discrete Math., 1992

The Greedy Algorithm is Optimal for On-Line Edge Coloring.
Inf. Process. Lett., 1992

The Competitiveness of On-Line Assignments.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality.
Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, 1992

Routing Strategies for Fast Networks.
Proceedings of the Proceedings IEEE INFOCOM '92, 1992

1991
An Efficient Parallel Algorithm for Computing a Large Independent Set in Planar Graph.
Algorithmica, 1991

Flow in Planar Graphs: A Survey of Results.
Proceedings of the Planar Graphs, 1991

1990
Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments.
SIAM J. Discrete Math., 1990

An Efficient Reconstruction of a Graph from its Line Graph in Parallel.
J. Algorithms, 1990

One-Bit Algorithms.
Distributed Computing, 1990

Small-bias Probability Spaces: Efficient Constructions and Applications
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Flow in Planar Graphs with Vertex Capacities.
Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, 1990

1989
On Separating the Erew and Crew Pram Models.
Theor. Comput. Sci., 1989

Fast Parallel Algorithms for Chordal Graphs.
SIAM J. Comput., 1989

Using Bounded Degree Spanning Trees in the Design of Efficient Algorithms on Claw-Free Graphs.
Proceedings of the Algorithms and Data Structures, 1989

An Efficient Parallel Algorithm for Computing a Large Independent Set in a Plan Graph.
SPAA, 1989

The Probabilistic Method Yields Deterministic Parallel Algorithms
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Flow in Planar Graphs with Multiple Sources and Sinks (Extended Abstract)
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988
A Fast Parallel Algorithm to Color a Graph with Delta Colors.
J. Algorithms, 1988

One Bit Algorithms.
Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, 1988

Computing a Perfect Matching in a Line Graph.
Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987
A Fast Parallel Coloring of Planar Graphs with Five Colors.
Inf. Process. Lett., 1987

Fast Parallel Algorithms for Chordal Graphs (Extended Abstract)
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1984
Multiple Resolution Texture Analysis and Classification.
IEEE Trans. Pattern Anal. Mach. Intell., 1984

1983
Hierarchical image representation for compression, filtering and normalization.
Pattern Recognition Letters, 1983

Image Compression and Filtering Using Pyramid Data Structures.
Proceedings of the 8th International Joint Conference on Artificial Intelligence. Karlsruhe, 1983


  Loading...