Country credit-risk rating aggregation via the separation-deviation model (with Erick Moreno), to appear Optimization Methods and Software.
Polynomial time algorithms for bi-criteria, multi-objective and ratio problems in clustering and imaging: Part I: Normalized cut and ratio regions. arXiv:0803.0146v1
A Computational Study of the Pseudoflow and Push-relabel Algorithms for the Maximum Flow Problem. (With Bala Chandran), Operations Research To appear.
The multi-integer set cover and the facility terminal cover problem (With Asaf Levin). Networks, to appear.
Covering the edges of bipartite graphs using K_{2,2} graphs (With Asaf Levin). In , C. Kaklamanis and M. Skutella (Eds.): WAOA 2007, LNCS 4927, pp. 116-127, 2008. Springer-Verlag Berlin Heidelberg 2008.
"The Inequality-Satisfiability problem." (with Erick Moreno). Operations Research Letters 36 (2008) 229-233. Available from journal, here
"Dynamic evolution of economically preferred facilities." To appear European J. of Operational Research.
"Ranking sports teams and the inverse equal paths problem." Proceedings 2nd international Workshop on Internet & Network Economics WINE06 Dec 2006. LNCS4286, pp 307-318
"Complexity and algorithms for nonlinear optimization problems." Annals of Operations Research 153, 257-296. 2007
"The Pseudoflow algorithm: A new algorithm for the maximum flow problem" Operations Research , to appear.
"Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms" (with Asaf Levin.) Discrete optimization , Volume 3, Issue 4 , 1 December 2006, Pages 327-340
"Solving Linear Cost Dynamic Lot Sizing Problems in O(n log n) Time" (with R. Ahuja), Operations Research , 56:1 Jan-Feb 2008, 255-261.
"Methodologies for the group rankings decision" (with Asaf Levin.) Management Science , Vol. 52, No. 9, September 2006, pp. 1394-1408.
"Complexity and algorithms for convex network optimization and other nonlinear problems". 4OR , 3:3, 2005, 171 - 216
"Optimizing over consecutive 1's and circular 1's constraints" (With Asaf Levin.). SIAM J on Optimization , Vol. 17, No. 2, pp. 311--330, 2006.
"Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today" Management Science Vol 50:6, pp 709-723, 2004.
"Due Date Quotation Models and Algorithms". (with P. Kaminsky) Handbook on Scheduling Algorithms, Methods, and Models, Joseph Y. Leung (ed.), Chapman Hall/CRC Press 2004. pp 20-1 -- 20-22.
"Monotonizing linear programs with up to two nonzeroes per column". Operations Research Letters, 2003, 32:1 pp 49-58.
"A Cut Based Algorithm for the Convex Dual of the Minimum Cost Network Flow Problem". (with Ravindra K. Ahuja and James B. Orlin). Algorithmica 39:3 189 - 208 (April) 2004.
"Efficient algorithms for the inverse spanning tree problem". Operations Research, September-October 2003, 51,:5, 785-797.
"Solving the convex cost integer dual of minimum cost network flow problem". (with Ravindra K. Ahuja and James B. Orlin). Management Science, 49:7, (2003) 950-964.
"The SONET edge partition problem". (with Olivier Goldschmidt, Asaf Levin and Eli V. Olinick). Networks,, Vol 41:1 (2003) pp. 13-23.
"Minimax problems with bitonic matrices" (with Paul A. Tucker) Networks. Vol 40, No 3, 2002 pp. 113-124.
"Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations" European Journal of Operational Research 140/2, 2002, pp. 291-321.
"An efficient algorithm for image segmentation, Markov Random Fields and related problems". Journal of the ACM. Vol 48, No 2, July 2001 pp. 686 - 701.
Book: Young Hae Lee, Mitsuo Gen and Dorit S. Hochbaum (eds.) "A focused issue on Supply Chain Management", Computers and Industrial Engineering Volume 43, Issue 1-2, Elsevier, (2002).
"Capacity acquisition, subcontracting, and lot sizing" (with Alper Atamturk). Management Science, Vol 47, No 8 August 2001 pp. 1-20.
"A new-old algorithm for minimum cut in closure graphs," Networks, Special 30th anniversary paper, Vol 37, No 4, 2001 171-193.
"Instant recognition of polynomial time solvability, half integrality and 2-approximations." Lecture Notes in Computer Science 1913, K.~Jansen and S.~Khuller (eds.). APPROX2000 proceedings pp 2-14, Sep 2000.
"Instant recognition of polynomial time solvability, half integrality and 2-approximations." EURO 17, Budapest 2000, pp 31-33.
"Improved Planning for the Open - Pit Mining Problem," (with A. Chen). Operations Research, 48:6, Nov -Dec 2000, 894-914,
"Minimizing a convex cost closure set". (with Maurice Queyranne). Siam Journal on Discrete Mathematics 16:2, 2003, pp 192-207. Extended abstract appeared in Lecture Notes in Computer Science 1879, M. Paterson (ed.), 8th Annual European Symposium on Algorithms - ESA 2000 proceedings pp 256-267.
"The Bounded Cycle Cover Problem" (with E. Olinick). Informs Journal on Computing, 13:2 spring 2001 104-119.
"Baseball, Optimization and the World Wide Web". (with I.Adler, A. Erera and E. Olinick). Interfaces 32:2 March-April 2002, pp. 12-22.
Book: Dorit Hochbaum, Klaus Jansen, Jose Rolim and Alistair Sinclair (eds.) "Randomization, Approximation and Combinatorial Optimization: Algorithms and Technique" Lecture Notes in Computer Science 1671, 1999.
"Approximating a Generalization of MAX 2SAT and MIN 2SAT". (with A. Pathria). Discrete Applied Mathematics, 107 (1-3) (2000) pp. 41-59.
"A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine" (with Fabian Chudak), Operations Research Letters, 25, (1999), 199-204.
"Solving a convex dual of minimum cost flow" (with Ravindra K. Ahuja and James B. Orlin). June 1999, Lecture Notes in Computer Science 1610, Cornuejols, Burkard and Woeginger (eds.). IPCO99 proceedings pp 31-44.
"An optimal algorithm for the Bottleneck transportation problem with a fixed number of sources". (with Gerhard J. Woeginger) Operations Research Letters, 24, (1999), 25-28.
"Approximating clique and biclique Problems". Journal of Algorithms 29, 1998, 174-200.
"The pseudoflow algorithm and the pseudoflow-based simplex for the maximum flow problem" Procdeedings of Integer Programming and Combinatorial Optimization 6th International IPCO conference, Houston Texas, June 1998, 325-337.
Instant recognition of half integrality and 2-approximation. " Procdeedings of APPROX98 Aalborg Denmark, July 1998.
"The t- vertex cover problem: Extending the half integrality framework with budget constraints." Procdeedings of APPROX98 Aalborg Denmark, July 1998.
"A primal-dual interpretation of recent 2-approximation algorithms for the feedback vertex set in undirected graphs" (with F. Chudak, M. Goemans and D. Williamson). Operations Research Letters 22, 111-118, (1998).
"Analysis of the Greedy Approach in Covering Problems," (with Anu Pathria). Naval Research Quarterly 45 (1998) 615-627.
"Locating centers in dynamically changing network and related problems" (with Anu Pathria), Location Science, 6 (1998) 243-256.
"Path Costs in Evolutionary Tree Reconstruction" (with Anu Pathria), Journal of computational biology 4(2), 1997, 163-175.
"Generalized p-Center Problems: Complexity Results and Approximation Algorithms," (with Anu Pathria), European Journal of Operational Research 100:3 1997, 594-607.
"Forest Harvesting and Minimum Cuts," (with A. Pathria). Forest Science, 43:4, Nov 1997, 544-554.
"The bottleneck Graph Partition Problem," (with A. Pathria), Networks 28:4, Dec 1996, 221-225.
"An Optimal Test Compression Procedure for Combinational circuits", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15:10, 1294-1299.
"k-edge Subgraph Problems," (with O. Goldschmidt). Discrete Applied Math Vol. 74, No. 2, pp. 159-169 (1997).
"Approximation algorithms for the k-Clique Covering Problem" (with O. Goldschmidt, C. Hurken and G. Yu). SIAM J. of Discrete Math, Vol 9:3, 492-509, August (1996).
"A new and fast approach to very large scale integrated sequential circuits test generation," (with Jeniffer Adams), Operations Research 45:6, 842-856, (1997).
"Approximation Algorithms for Network Design Problems on Bounded Subsets," (with Seffi Naor). J. of Algorithms, 21, 403-414 (1996).
"Algorithms and Heuristics for Scheduling
Semiconductor Burn-in Operations," (with D. Landy), August (1994),
Operations Research 45:6, 874-885, (1997).
"Scheduling with Batching: Two Job
Types" (with D. Landy),
Discrete Applied Math, 72, 99-114,
(1997).
"A Nonlinear Knapsack Problem,",
Operations Research Letters 17 (1995) 103-110.
"About Strongly Polynomial Time Algorithms for Quadratic
Optimization Over Submodular Constraints," (with S.P. Hong).
Mathematical Programming 69, (1995) 269-309.
"On the Complexity of the Production-Transportation Problem, (with
S.P. Hong). SIAM J. on optimization, Vol 6, No 1, 250-264, (1996).
"Scheduling with Batching:
Minimizing the Weighted Number of Tardy Jobs," (with D. Landy),
Operations Research Letters, 16 (1994) 79-86.
"An O(log k) approximation algorithm for the k-minimum spanning
tree problem in the plane," (with N. Garg).
Proceedings of the 26th Annual ACM
Symposium on the Theory of Computing (STOC) (1994) 432-438.
To appear Algorithmica.
"A Modified Greedy Heuristic for the Set Covering Problem with
Improved Worst Case Bound" (with O. Goldschmidt, and G. Yu),
Information Processing Letters 48 (1993) 305-310.
"Complexity and Algorithms for Logical Constraints with
Applications to VLSI Layout, Compaction and Clocking". Studies in
Locational Analysis, ISOLDE VI proceedings, 159-164 June (1993).
"Tight Bounds and 2-approximation Algorithms for Integer Programs
with Two Variables Per Inequality," (with N. Megiddo, J. Naor and A.
Tamir), Mathematical Programming, 62 (1993) 69-83.
"Polynomial Algorithms for Convex Network Optimization," in
Network Optimization Problems: Algorithms, Complexity
and Applications, edited by D. Du and P. M. Pardalos, World
Scientific, 63-92, (1993).
"Lower and Upper Bounds for the Allocation Problem and Other
Nonlinear Optimization Problems," Mathematics of Operations
Research, Vol. 19, No 2, 390-409, May (1994).
"A Polynomial Algorithm for the K-Cut Problem" (with 0.
Goldschmidt), Mathematics of Operations
Research Vol 19. No. 1 Feb (1994) 24-37.
"The Empirical Performance of a Polynomial Algorithm for
Constrained Nonlinear Optimization" (with S. Seshadri),
Annals of Operations
Research, Vol. 43 (eds. G. Mitra and I. Maros), 229-248, (1993).
"Simple and Fast Algorithms for Linear and Integer Programs
with Two Variables per Inequality," (with J. Naor)
SIAM Journal on Computing vol 23 No. 6, (1994), 1179-1192.
(earlier version in Proceedings of
IPCO, Second Integer Programming and Combinatorial Optimization
Conference, Carnegie Mellon University, May 1992, 41-60.)
"A Strongly Polynomial Algorithm for the Quadratic Transportation
Problem with Fixed Number of Suppliers" (with S. Cosares),
Mathematics of Operations Research Vol
19. No. 1 Feb (1994) 94-111.
"An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint
Paths and Communication Problems on Random Graphs," August 1988,
Operations Research, Vol. 40, No. 5, pp. 923-935, (1992).
"Why Should Biconnected Components Be Identified First,"
Discrete Applied Mathematics, 42, (1993), 203-210.
"The Multicovering Problem" (with N. Hall),
European Journal on Operational Research, 62, (1992) 323-339.
"A Polynomial Algorithm for an Integer Quadratic Nonseparable
Transportation Problem" (with J. G. Shanthikumar and R. Shamir),
Mathematical Programming, Vol. 55, No. 3, pp. 359-372, (1992).
"On the Impossibility of Strongly Polynomial Algorithms for the
Allocation Problem and its Extensions," Proceedings of the Integer
Programming and Combinatorial Optimization Conference, May 1990, 261-
274.
"Strongly Polynomial Algorithms for the High Multiplicity
Scheduling Problems" (with R. Shamir), Operations Research, Vol.
39, No. 4, (1991), 648-653.
"Nonlinear Separable Optimization is Not Much Harder than Linear
Optimization" (with J.G. Shanthikumar), Journal of ACM, Vol. 37,
No. 4 (1990), 843-862.
"The Complexity of Nonlinear Optimization" (with J. G.
Shanthikumar), Lecture Notes in Computer Science, 372, Springer-Verlag,
July 1989, pp. 461-472.
"Asymptotically Optimal Linear Algorithms for the Minimum K-Cut in
a Random Graph" (with O. Goldschmidt), SIAM J. on Discrete
Mathematics, February 1990, Vol. 3, No. 1, pp. 58-73.
"A Fast Perfect Matching Algorithm in Random Graphs" (with O.
Goldschmidt), SIAM J. on Discrete Mathematics, February 1990,
Vol. 3, No. 1, pp. 48-57.
"Minimizing the Number of Tardy Job Limits under Release Time
Contraints" (with R. Shamir), Discrete Applied Mathematics, Vol.
28 (1990), 45-57.
"O(nlog^2 n) Algorithm for the Maximum Weighted Tardiness Problem"
(with R. Shamir), Information Processing Letters, 31 (1989),
215-219.
"An Algorithm for the Detection and Construction of Monge
Sequences" (with A. Alon, S. Cosares and R. Shamir), Linear Algebra
and its Applications, 114/115 (1989), 669-680.
"A Polynomial Algorithm for the K-cut Problem" (with O.
Goldschmidt), Proceedings of 29th Annual Symposium on Foundations of
Computer Science (October 1988), pp. 444-451.
"A Best Possible Parallel Approximation Algorithm to a Graph
Theoretic Problem" (with D. Shmoys), Operational Research
(1987), 933- 938.
"Analysis of a Flow Problem with Fixed Charges" (with A. Segev),
Networks, Vol. 19 (1989), 291-312.
"A Polynomial Approximation Scheme for Machine Scheduling on
Uniform Processors: Using the Dual Approximation Approach" (with D.
Shmoys), SIAM J. on Computing, 17:3 (1988), 539-551.
"The Concept of Best Possibility on the Analysis of Approximation
Algorithms," Proceedings of the Israel Mathematical Union Conference,
Tel-Aviv University, Israel (1987), 36-42.
"Fast Approximation Algorithms for a Non-Convex Covering Problem"
(with W. Maass), Journal of Algorithms, 8 (1987), 305-323.
"Lagrangian Relaxation for Testing Infeasibility in VLSI Routing"
(with T. Feo), Operations Research, 34:6 (1986).
"A Fast Approximation Algorithm for the Multicovering Problem"
(with N. Hall), Discrete Applied Mathematics, 15 (1986), 35-40.
"A Packing Problem You Can Almost Solve by Sitting on Your
Suitcase" (with D. Shmoys), SIAM Journal on Algebraic and Discrete
Methods, 7:2 (April 1986), 247-257.
"Using Dual Approximation Algorithms for Scheduling Problems:
Practical and Theoretical Results" (with D. Shmoys), Journal of
ACM, 34:1 (January 1987), 144-162.
"The Linzertorte Problem - Or a Unified Approach to Painting,
Baking and Weaving" (with E. Wigderson), Discrete Applied
Mathematics, 14 (1986), 17-32.
"A Unified Approach to Approximation Algorithms for Bottleneck
Problems" (with D. Shmoys), Journal of ACM, 33:3 (July 1986),
533-550.
"An O(V2) Algorithm for the Planar 3-Cut Problem" (with D.
Shmoys), SIAM Journal on Algebraic and Discrete Methods, 6:4 (1985),
707-712.
"A Better than 'Best Possible' Algorithm to Edge Color
Multigraphs" (with D. Shmoys and T. Nishizeki), Journal of Algorithms,
7:1 (March 1986), 79-104.
"A Best Possible Heuristic for the K-Center Problem" (with D.
Shmoys), Mathematics of Operations Research, 10:2 (May 1985), 180-184.
"Approximation Schemes for Covering and Packing Problems in Image
Processing and VLSI" (with W. Maass), Journal of ACM, 32:1 (January
1985), 130-136.
"Best Possible Heuristics for the Bottleneck Wandering Salesperson
and Bottleneck Vehicle Routing Problems" (with D. Shmoys), European
Journal of Operational Research, 26 (1986), 380-384.
"Easy Solutions for the K-Center Problem or the Dominating Set
Problem on Random Graphs," Annals of Discrete Mathematics, 25 (1985),
189-210.
"Approximation Schemes for Covering and Packing Problems in
Robotics and VLSI" (with W. Maass), Springer-Verlag Lecture Notes in
Computer Science, 166 (April 1984).
"Powers of Graphs: A Powerful Approximation Algorithm Technique"
(with D. Shmoys), Proceedings of the Symposium on Theory of Computing,
May 1984.
"When are NP-hard Location Problems Easy," Annals of Operations
Research, 1 (1984), 201-214.
"Efficient Bounds for the Stable Set, Vertex Cover and Set Packing
Problems," Discrete Applied Mathematics, 6 (1983), 243-254.
"On the Fractional Solution to the Set Covering Problem," SIAM
Journal of Algebraic and Discrete Methods, 4:2 (1983), 221-222.
"Approximation Algorithms for the Weighted Set Covering and Node
Cover Problems," GSIA Working Paper No. 64-79-80, April 1980; also,
SIAM Journal of Computing, 11:3 (1982), 555-556.
"Steinhaus' Geometric Location Problem for Random Samples in the
Plane" (with J. Michael Steele), Advanced Applied Probability, 14
(1982), 56-67.
"Heuristics for the Fixed Cost Median Problem," Mathematical
Programming, 22:2 (1982), 148-162.
"Database Location in Computer Networks" (with M.L. Fisher),
Journal of the Association for the Computing Machinery, 27:4 (October
1980).
"Probabilistic Analysis of the Euclidean K-Median Problem" (with
M.L. Fisher), Mathematics of Operations Research, 5:1 (February 1980).
"A Quantitative Analysis of Astigmatism Induced by Pterygium"
(with S. Moskowitz and J. Wirtschafter), Journal of Biomechanics, 10
(1977), 735-46.